http://blog.csdn.net/lanchunhui/article/details/51112862

機(jī)器學(xué)習(xí)基礎(chǔ)—— 遺傳算法（GA）

機(jī)器學(xué)習(xí)（123） 

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

遺傳算法（Genetic Algorithms）也是受自然科學(xué)的啟發(fā)。該類(lèi)算法的運(yùn)行過(guò)程是先隨機(jī)生成一組解，稱(chēng)之為種群（population）。在優(yōu)化過(guò)程中的每一步，算法會(huì)計(jì)算整個(gè)種群的成本函數(shù)，從而得到一個(gè)有關(guān)題解的有序列表。

其三個(gè)主要特性在于：

在對(duì)題解進(jìn)行排序之后，一個(gè)新的種群——我們稱(chēng)之為下一代——被創(chuàng)建出來(lái)了。首先，我們將當(dāng)前種群中位于最頂端的題解加入其所在的新種群中。我們稱(chēng)這一過(guò)程為精英選拔（elitism）。新種群的余下部分是由修改最優(yōu)解后形成的全新解所組成的。

有兩種修改題解的方法。

（1）較為簡(jiǎn)單的一種稱(chēng)為變異（mutation），其通常的做法是對(duì)一個(gè)既有解進(jìn)行微小的、簡(jiǎn)單的、隨機(jī)的改變。

（2）另一種方法稱(chēng)為交叉（crossover）或配對(duì)（breeding）。這種方法是選取最優(yōu)解中的兩個(gè)解，然后將它們按照方式結(jié)合。

算法設(shè)計(jì)中可能涉及的參數(shù)主要有，

遺傳算法的程序還是比較好寫(xiě)的，因?yàn)榱鞒谭浅９潭ǎ?/p>def geneticalgo(domains, costf, popsize=100, mutprob=.2, elite=.2, maxiter=100): def mutable(c): i = random.randint(0, len(domains)-1) if random.random() < 0.5 and c[i] > domains[i][0]: c[i] -= 1 elif c[i] < domains[i][1]: c[i] += 1 return c def crossover(r1, r2): i = random.randint(1, len(domains)-2) return r1[:i] + r2[i:] pop = [] for i in range(popsize): r = [random.randint(domains[i][0], domains[i][1]) for i range(len(domains))] pop.append(r) topelite = int(popsize*elite) for i in range(maxiter): scores = [(costf(r), r) for r in pop] scores.sort() randked = [v for c, v in scores] pop = ranked[:topelite] while (len(pop) < popsize): if random.random() < mutprob: r = random.randint(0, topelite-1) pop.append(mutable(pop[r])) else: c1 = random.randint(0, topelite-1) c2 = random.randint(0, topelite-1) pop.append(crossover(pop[c1], pop[c2])) print(scores[0][1]) return scores[0][0]