我的《自然計算》作業(yè)，搬上來怨咪。
目錄
- 概述
- 編碼
- 初始群體的產(chǎn)生
- 適應度計算
- 選擇運算
- 交叉運算
- 變異運算
- 測試效果
參考資料
一，概述
本文在理解遺傳算法的基本原理的基礎上，使用Java語言寫了一個小程序來簡單實現(xiàn)用遺傳算法求解二次函數(shù)f(x,y)=xx+yy (x和y的取值范圍為1到127的正整數(shù))的最大值泳挥。完整源碼見已上傳至我的github，詳情請點擊此鏈接：查看本項目全部代碼
二至朗，編碼
重述一下本文求解的問題：
由于遺傳算法的運算對象是表示個體的符號串屉符，所以必須把變量x,y編碼為一種符號串。在這里采用無符號二進制整數(shù)來表示锹引。因x,y的取值范圍為1到127,矗钟，則可用兩個7位二進制數(shù)來分別表示它們。而一個基因就是一個14位二進制串嫌变。例如吨艇，基因型00000001111111所對應的表現(xiàn)型是：x=0,y=127。在代碼中的具體體現(xiàn)為：設計類Chromosome腾啥，其具有私有整形字段x,y表示x,y的十進制值秸应、String字段gene表示二進制串。并使用常量定義其最大值或最大長度碑宴。代碼如下：
public static final int GENG_LENGTH = 14;
public static final int MAX_X = 127;
public static final int MAX_Y = 127;
private int x,y;
private String gene;
三软啼，初始群體的產(chǎn)生
遺傳算法是對群體進行的進化操作，所以第一步要產(chǎn)生一個初始種群延柠，再進行后續(xù)的交叉祸挪、變異、選擇等操作贞间。在具體實現(xiàn)上贿条，初始種群的產(chǎn)生較為簡單。首先對類Chromosome進行構(gòu)造函數(shù)的編寫增热，主要寫了以下兩種構(gòu)造函數(shù)：
public Chromosome(String gene) //給定基因串構(gòu)造染色體
public Chromosome(int x,int y) //給定表現(xiàn)型構(gòu)造染色體
在這里用到了第二個構(gòu)造函數(shù)整以，首先隨機產(chǎn)生兩個1到127之間的數(shù)作為X,Y，再調(diào)用構(gòu)造函數(shù)生成新染色體并添加到初始種群中去峻仇。如此重復公黑，直到種群規(guī)模達到要求。具體代碼如下:
public static ArrayList<Chromosome> initGroup(int size) {
ArrayList<Chromosome> list = new ArrayList<Chromosome>();
Random random = new Random();
for(int i = 0; i < size; i++) {
int x = random.nextInt() % 128;
int y = random.nextInt() % 128;
x = x < 0? (-x):x;
y = y < 0? (-y):y;
list.add(new Chromosome(x,y));
}
return list;
}
四，適應度計算
遺傳算法中以個體適應度評價其優(yōu)劣程度凡蚜，其最終目的是選擇出適應度較高的個體人断。本文所求解問題，目標函數(shù)總?cè)》秦撝党⑶沂且郧蠛瘮?shù)最大值為優(yōu)化目標恶迈，故可直接利用目標函數(shù)值作為個體的適應度。具體求解代碼如下：
public int calcFitness() {
return x*x+y*y;
}
五谱醇，選擇運算
選擇運算把當前的群體中適應度較高的個體按照某種規(guī)則或模型遺傳到下一代個體中暇仲。這里我們使用課堂上講的“輪盤賭”的方式進行選擇「笨剩“輪盤賭”的思想這里不再贅述奈附，只說一下JAVA代碼的具體實現(xiàn)過程。
首先計算種群中每個個體的適應度保存到一個數(shù)組里佳晶。在這基礎上計算“累加適應度”桅狠，即第一個適應度為原第一個適應度，第二個為前兩個的和轿秧，第三個為前三個的和中跌，以此類推。再將此數(shù)組每個元素除以總的適應度菇篡。然后進行選擇漩符，選擇次數(shù)和設定好的種群規(guī)模相同（這樣便可以控制種群的規(guī)模不會無限的上漲）。每次選擇時驱还，先產(chǎn)生一個0到1之間的隨機數(shù)嗜暴。在上述數(shù)組中遍歷找到第一個大于此隨機數(shù)的元素，這個元素對應的個體被選擇议蟆。具體代碼如下：
public static ArrayList<Chromosome> selector(ArrayList<Chromosome> fatherGroup,int sonGroupSize)
{
ArrayList<Chromosome> sonGroup = new ArrayList<Chromosome>();
int totalFitness = 0;
double[] fitness = new double[fatherGroup.size()];
for(Chromosome chrom : fatherGroup) {
totalFitness += chrom.calcFitness();
}
int index = 0;
//計算適應度
for(Chromosome chrom : fatherGroup) {
fitness[index] = chrom.calcFitness() / ((double)totalFitness);
index++;
}
//計算累加適應度
for(int i = 1; i < fitness.length; i++) {
fitness[i] = fitness[i-1]+fitness[i];
}
//輪盤賭選擇
for(int i = 0; i < sonGroupSize; i++) {
Random random = new Random();
double probability = random.nextDouble();
int choose;
for(choose = 1; choose < fitness.length - 1; choose++) {
if(probability < fitness[choose])
break;
}
sonGroup.add(new Chromosome(fatherGroup.get(choose).getGene()));
}
return sonGroup;
}
六闷沥，交叉運算
交叉運算是遺傳算法中產(chǎn)生新個體的主要操作過程，它以某一概率相互交換某兩個個體之間的部分染色體咐容。本文采用單點交叉的方法舆逃，具體操作過程是：先對群體進行隨機配對；其次隨機設置交叉點位置戳粒；最后再相互交換配對染色體之間的部分基因路狮。
具體的算法流程按照老師課件上講的，這里也不贅述了蔚约。只說一下具體代碼實現(xiàn)原理奄妨。這個算法的要點在于隨機配對個體進行交叉、字符串的拼接操作和生成新個體苹祟。隨機配對可以使用一個do while循環(huán)砸抛，選擇兩個不同的個體评雌。然后隨機選取交叉點，進行兩個基因字符串的交叉锰悼。最后生成新的個體柳骄，采用以下構(gòu)造函數(shù)生成新的個體：public Chromosome(String gene)团赏。
具體代碼如下：
public static ArrayList<Chromosome> corssover(ArrayList<Chromosome> fatherGroup,double probability) {
ArrayList<Chromosome> sonGroup = new ArrayList<Chromosome>();
sonGroup.addAll(fatherGroup);
Random random = new Random();
for(int k = 0; k < fatherGroup.size() / 2; k++) {
if(probability > random.nextDouble()) {
int i = 0,j = 0;
do {
i = random.nextInt(fatherGroup.size());
j = random.nextInt(fatherGroup.size());
} while(i == j);
int position = random.nextInt(Chromosome.GENG_LENGTH);
String parent1 = fatherGroup.get(i).getGene();
String parent2 = fatherGroup.get(j).getGene();
String son1 = parent1.substring(0, position) + parent2.substring(position);
String son2 = parent2.substring(0, position) + parent1.substring(position);
sonGroup.add(new Chromosome(son1));
sonGroup.add(new Chromosome(son2));
}
}
return sonGroup;
}
七箕般，變異運算
變異運算是對個體的某一個或某一些基因按某一較小的概率進行改變，它也是產(chǎn)生新個體的一種操作方法舔清。本文中我們采用如下方式進行變異：遍歷群體中所有個體的所有基因位丝里，以一個較小的概率對每個基因位進行變異操作即1變成0,0變成1。在Java代碼中具體實現(xiàn)時体谒，我們先編寫一個函數(shù)對一個個體的基因進行改變杯聚，即用新基因串代替舊基因串。該函數(shù)編寫如下：
public void selfMutation(String newGene) {
if(newGene.length() != Chromosome.GENG_LENGTH)
return;
this.gene = newGene;
String xStr = newGene.substring(0, Chromosome.GENG_LENGTH/2);
String yStr = newGene.substring(Chromosome.GENG_LENGTH/2);
this.x = Integer.parseInt(xStr,2);
this.y = Integer.parseInt(yStr,2);
}
然后抒痒，按照上述說法對每一位基因進行遍歷幌绍，按指定概率進行變異操作。具體代碼如下所示：
public static void mutation(ArrayList<Chromosome> fatherGroup,double probability) {
Random random = new Random();
Chromosome bestOne = Chromosome.best(fatherGroup);
fatherGroup.add(new Chromosome(bestOne.getGene()));
for(Chromosome c : fatherGroup) {
String newGene = c.getGene();
for(int i = 0; i < newGene.length();i++){
if(probability > random.nextDouble()) {
String newChar = newGene.charAt(i) == '0'?"1":"0";
newGene = newGene.substring(0, i) + newChar + newGene.substring(i+1);
}
}
c.selfMutation(newGene);
}
}
八故响，測試效果
以上實現(xiàn)了所有子模塊傀广。下面使用上述模塊進行實際的遺傳算法求解操作。首先產(chǎn)生初始種群彩届，按照交叉伪冰、變異、選擇的順序進行循環(huán)樟蠕，直到選出符合要求的個體贮聂，這里設置的條件為適應度大于等于32258時終止，這也是本題中能達到的最大適應度寨辩。
final int GROUP_SIZE = 20;//種群規(guī)模
final double CORSSOVER_P = 0.6;//交叉概率
final double MUTATION_P = 0.01;//變異概率
ArrayList<Chromosome> group = Chromosome.initGroup(GROUP_SIZE);
Chromosome theBest;
do{
group = Chromosome.corssover(group, CORSSOVER_P);
Chromosome.mutation(group, MUTATION_P);
group = Chromosome.selector(group, GROUP_SIZE);
theBest = Chromosome.best(group);
System.out.println(theBest.calcFitness());
}while(theBest.calcFitness() < 32258);
如上述代碼所示吓懈，在每次迭代后輸出當前種群中的最優(yōu)個體。下面進行了三次測試靡狞。最優(yōu)個體適應度隨種群代數(shù)變化圖耻警，如下圖所示（三次的結(jié)果）∷Ｈ粒可以看出隨著迭代次數(shù)的增加榕栏，種群中的最優(yōu)個體適應度總體呈上升趨勢，最終一般在50代之內(nèi)就會找到滿足要求的個體蕾各。
參考資料：
[1]遺傳算法的例子 http://blog.csdn.net/b2b160/article/details/4680853/
[2]老師的課件 cn01-IntroGA-v1.00.ppt
