遺傳算法的基本運(yùn)算過(guò)程是用循環(huán)語(yǔ)句控制不同的五個(gè)步驟。
一、編碼赫舒、隨機(jī)產(chǎn)生初始群體
- 編碼的好壞關(guān)系到求解的速度羊娃。
- 遺傳算法的工作對(duì)象是字符串唐全,對(duì)字符串的編碼要求是:字符串要反映所研究問(wèn)題的特性;字符串的表達(dá)式要便于計(jì)算機(jī)處理蕊玷。
二邮利、個(gè)體評(píng)價(jià)、選擇垃帅、確定是否輸出
- 設(shè)計(jì)一個(gè)適應(yīng)度函數(shù)延届,進(jìn)行個(gè)體評(píng)價(jià)。
- 把優(yōu)秀的留下使其比例增大贸诚,把差的篩選掉方庭。
- 在遺傳算法中,衡量個(gè)體優(yōu)劣的尺度是適應(yīng)度酱固,根據(jù)適應(yīng)度的大小決定個(gè)體繁殖的數(shù)量械念、或決定其是否消亡。適應(yīng)度是驅(qū)動(dòng)遺傳算法的動(dòng)力运悲。
- 復(fù)制算子將優(yōu)良個(gè)體在下一代予以繁殖龄减,個(gè)體被復(fù)制的數(shù)量是按照適應(yīng)度的大小決定的,群體中個(gè)體總數(shù)是不變的班眯。
- 采用等差希停、等比或者輪盤(pán)賭的復(fù)制方式,防止過(guò)早的收斂署隘。
三宠能、隨機(jī)交叉運(yùn)算
- 對(duì)已經(jīng)存在下的個(gè)體進(jìn)行隨機(jī)交換交叉運(yùn)算。
- 交換是遺傳算法中產(chǎn)生新個(gè)體的主要手段磁餐,將兩個(gè)個(gè)體的部分字符互相交換违崇。
- 執(zhí)行交換的個(gè)體是隨機(jī)選擇的。
- 交換的概率一般為50~80%(可以根據(jù)實(shí)際情況靈活選擇)崖媚。
四亦歉、隨機(jī)變異運(yùn)算
- 對(duì)已經(jīng)存在下的個(gè)體進(jìn)行隨機(jī)、變異叉運(yùn)算畅哑。
- 變異是遺傳算法中產(chǎn)生新個(gè)體的方法(不是最主要的方法)肴楷,將被選擇的個(gè)體的部分字符進(jìn)行補(bǔ)運(yùn)算。
- 變異個(gè)體是隨機(jī)選擇的荠呐。
- 個(gè)體的第幾位開(kāi)始變異是隨機(jī)的
- 個(gè)體變異幾位也是隨機(jī)的赛蔫。
五砂客、轉(zhuǎn)向個(gè)體評(píng)價(jià),開(kāi)始新循環(huán)
- 最常用的終止條件是迭代的代數(shù)呵恢。
- 當(dāng)目標(biāo) 函數(shù)有最優(yōu)目標(biāo)值時(shí)鞠值,可采用控制偏差的方式實(shí)現(xiàn)。
- 檢查適應(yīng)度的變化渗钉。
模式理論
- 編碼是左邊(高位)數(shù)字越小彤恶,其適應(yīng)度將越大。這種字符串的形式特征叫做編碼模式鳄橘。
- 模式中確定的字符的個(gè)數(shù)就叫做模數(shù)的階數(shù)声离。模數(shù)階數(shù)越低,代表的字符串的個(gè)數(shù)就越多瘫怜。
- 模式中最前面和最后面兩個(gè)確定字符的距離稱(chēng)為模式的長(zhǎng)度术徊。
遺傳過(guò)程中的模式數(shù)目與模式定理
- 復(fù)制時(shí)的模式數(shù)目
H模式編碼在每一代復(fù)制的過(guò)程中以指數(shù)的方式增加。 - 經(jīng)過(guò)復(fù)制鲸湃、交換赠涮、突變?cè)谙乱淮鷵碛械膫€(gè)數(shù)公式。t+1代的數(shù)目和t代數(shù)目暗挑、平均適應(yīng)度成正比笋除。
- 模式定理表明:長(zhǎng)度短、階次低窿祥、平均適應(yīng)度大的模式在遺傳算法循環(huán)中呈指數(shù)增長(zhǎng)株憾。(從理論上保證了遺傳算法是智能的搜素)蝙寨。