#?-*-?coding:?utf-8?-*-

import?random
import?math

SCORE_NONE?=?-1

class?Life（object）:
??????“““個體類“““
??????def?__init__（self?aGene?=?None）:
????????????self.gene?=?aGene
????????????self.score?=?SCORE_NONE

class?GA（object）:
??????“““遺傳算法類“““
??????def?__init__（self?aCrossRate?aMutationRage?aLifeCount?aGeneLenght?aMatchFun?）:
????????????#lambda作為一個表達式，定義了一個匿名函數
????????????self.croessRate?=?aCrossRate
????????????self.mutationRate?=?aMutationRage
????????????self.lifeCount?=?aLifeCount
????????????self.geneLenght?=?aGeneLenght
????????????self.matchFun?=?aMatchFun?????????????????#?適配函數
????????????self.lives?=?[]???????????????????????????#?種群
????????????self.best?=?None??????????????????????????#?保存這一代中最好的個體
????????????self.generation?=?1
????????????self.crossCount?=?0
????????????self.mutationCount?=?0
????????????self.bounds?=?0.0????????????????????????#?適配值之和，用于選擇是計算概率
????????????self.mean?=?1.0???????????????????????????#?適配值平均值
????????????self.initPopulation（）


??????def?initPopulation（self）:
????????????“““初始化種群“““
????????????self.lives?=?[]
????????????for?i?in?range（self.lifeCount）:
??????????????????gene?=?[?x?for?x?in?range（self.geneLenght）?]?
??????????????????random.shuffle（gene）#用來對一個元素序列進行重新隨機排序
??????????????????life?=?Life（gene）
??????????????????self.lives.append（life）


??????def?judge（self）:
????????????“““評估，計算每一個個體的適配值“““
????????????self.bounds?=?0.0
????????????self.best?=?self.lives[0]
????????????for?life?in?self.lives:
??????????????????life.score?=?self.matchFun（life）
??????????????????self.bounds?+=?life.score
??????????????????if?self.best.score?????????????????????????self.best?=?life
????????????self.mean=self.bounds/self.lifeCount


??????def?cross（self?parent1?parent2）:
????????????“““交叉“““
????????????n=0
????????????while?1:
??????????????????newGene?=?[]

??????????????????index1?=?random.randint（0?self.geneLenght?-?1）#用于生成一個指定范圍內的整數
??????????????????index2?=?random.randint（index1?self.geneLenght?-?1）
??????????????????tempGene?=?parent2.gene[index1:index2]???#?交叉的基因片段
??????????????????p1len?=?0
??????????????????for?g?in?parent1.gene:
????????????????????????if?p1len?==?index1:
??????????????????????????????newGene.extend（tempGene）?????#?插入基因片段
??????????????????????????????p1len?+=?1
????????????????????????if?g?not?in?tempGene:
??????????????????????????????newGene.append（g）
??????????????????????????????p1len?+=?1
??????????????????if?（self.matchFun（Life（newGene））?>?max（self.matchFun（parent1）self.matchFun（parent2）））:
????????????????????????self.crossCount?+=?1
????????????????????????return?newGene
??????????????????#?else:
??????????????????#???????rate?=?random.random（）
??????????????????#???????if?rate???????????????????#?????????????self.crossCount?+=?1
??????????????????#?????????????return?newGene
??????????????????if?（n>100）:
????????????????????????self.crossCount?+=?1
????????????????????????return?newGene
???

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2017-12-28?13:40??GA-TSP\
?????文件????????5328??2017-12-13?03:30??GA-TSP\GA.py
?????文件????????2895??2017-12-06?09:40??GA-TSP\TSP_GA.py