Posted on 2007-04-26 21:41
Zou Ang 閱讀(7049)
評(píng)論(14) 編輯 收藏 所屬分類(lèi):
最近學(xué)習(xí)遺傳算法，寫(xiě)了這么一個(gè)小程序來(lái)計(jì)算函數(shù) f(x,y,z) = xyz*sin(xyz)的最大值，這段程序經(jīng)過(guò)小小改變就可以適應(yīng)其他的函數(shù)最大值求解問(wèn)題
首先介紹一下遺傳算法，遺傳算法就是模擬自然界中物競(jìng)天擇，適者生存的法則，通過(guò)對(duì)解空間進(jìn)行進(jìn)化從而求得最優(yōu)方案的方法，遺傳算法的好處在于，即使算法中的某些參數(shù)不起作用了，整個(gè)算法還是可以正常地工作，也就是說(shuō)，整體種群的走向是越來(lái)越好的
遺傳算法的關(guān)鍵內(nèi)容包括：
1. 染色體
首先對(duì)優(yōu)化問(wèn)題的解進(jìn)行編碼，編碼后的一個(gè)解被稱(chēng)為一個(gè)染色體，組成染色體的元素稱(chēng)為基因。比如對(duì)于上面那個(gè)函數(shù)，我們就可以用24位的2進(jìn)制串進(jìn)行編碼，首先8位2進(jìn)制數(shù)代表x,中間為y,最后為z，x,y,z都屬于[0,255]
2. 交配
將兩個(gè)染色體進(jìn)行交叉的操作被稱(chēng)為交配，交配可能提高染色體的適應(yīng)值，也可能降低其適應(yīng)值。通常交配是以一定的概率發(fā)生的。在程序中，我們通過(guò)隨機(jī)交換兩個(gè)染色體的一些位來(lái)體現(xiàn)。
3. 適應(yīng)函數(shù)
我們需要使用一個(gè)函數(shù)來(lái)表現(xiàn)解的優(yōu)異程度，這個(gè)函數(shù)只要可以反映出解的優(yōu)劣即可，沒(méi)必要很精確。適應(yīng)函數(shù)就類(lèi)似我們生存的環(huán)境，環(huán)境評(píng)估我們的生存能力，評(píng)估值高的更容易存活。
4. 變異
有時(shí)候種群中的某些個(gè)體會(huì)發(fā)生變異的現(xiàn)象，變異一般是以很小的概率發(fā)生的，但是變異增加了種群進(jìn)化的不確定性，也讓種群中的個(gè)體類(lèi)型更加豐富。在程序中，我們用隨機(jī)變化某一位來(lái)體現(xiàn)。
算法的流程為：
1.初始化種群
2.進(jìn)行第一輪評(píng)估
3.交配
4.變異
5.評(píng)估
6.重新選擇種群
7.若未達(dá)到結(jié)束條件，轉(zhuǎn)3
隨機(jī)數(shù)生成器：
package edu.zsu.zouang.util;
import java.util.Random;
public class Randomizer 
{
private int lower;
private int upper;
private static Random random = new Random();
public Randomizer(int lower, int upper){
if(upper <= lower){
throw new IllegalStateException("Upper is smaller than lower!");
}
this.lower = lower;
this.upper = upper;
}
public Double nextDouble(){
return Double.valueOf(lower + (upper - lower) * random.nextDouble());
}
public Integer nextInteger(){
return Integer.valueOf(lower +random.nextInt(upper - lower));
}
public char[] nextBitArray(int length){
if(length <= 0){
throw new IllegalStateException("Length is less than ZERO!");
}
char[] temp = new char[length];
for(int i = 0; i < length ; i++){
temp[i] = random.nextBoolean() ? '1' : '0';
}
return temp;
}
}
染色體：
package edu.zsu.zouang.inheritence;
import java.util.Arrays;
import edu.zsu.zouang.util.Randomizer;
public class Chromosome implements Cloneable{
private double fitness = -1; //代表未計(jì)算適應(yīng)函數(shù)
private double select = -1; // 選擇概率
private char[] chromo; //染色體串
private Randomizer random;
private int lower;
private int upper;
public Chromosome(int lower, int upper, int length){
this.lower = lower;
this.upper = upper;
random = new Randomizer(lower, upper);
chromo = random.nextBitArray(length);
}
/** *//**
* 克隆一個(gè)染色體
*/
public Chromosome clone(){
Chromosome c = new Chromosome(lower,upper,chromo.length);
char[] temp = new char[c.chromo.length];
System.arraycopy(chromo, 0, temp, 0, chromo.length);
c.setChromo(temp);
return c;
}
public char[] getChromo() {
return chromo;
}
public void setChromo(char[] chromo) {
this.chromo = chromo;
}
public double getFitness() {
return fitness;
}
public void setFitness(double fitness) {
this.fitness = fitness;
}
public double getSelect() {
return select;
}
public void setSelect(double select) {
this.select = select;
}
}
適應(yīng)函數(shù)接口：
package edu.zsu.zouang.inheritence;
public interface FitnessCalculate {
public double calculate(char[] chromosome);
}
本函數(shù)的適應(yīng)函數(shù)，既然是求最大值，干脆用求解的函數(shù)來(lái)做適應(yīng)函數(shù)
package edu.zsu.zouang.inheritence;
/** *//**
* 計(jì)算xyz*sin(xyz)最大值的遺傳函數(shù)適應(yīng)值
* 2007-4-25
* @author Zou Ang
* Contact <a href ="mailto:richardeee@gmail.com">Zou Ang</a>
*/
public class FunctionFitness implements FitnessCalculate {
public double calculate(char[] chromosome) {
/**//*
* x、y、z都用8位來(lái)編碼，即x,y,z都屬于[0,255]
*/
double x = 0;
double y = 0;
double z = 0;
for(int i = 0; i < 8; i++){
int j = i + 8;
int k = i + 16;
x = x + Math.pow(2, 7 - i) * (Integer.valueOf(chromosome[i]) - 48);
y = y + Math.pow(2, 7 - i) * (Integer.valueOf(chromosome[j]) - 48);
z = z + Math.pow(2, 7 - i) * (Integer.valueOf(chromosome[k]) - 48);
}
return x * y * z * Math.sin(x*y*z);
}
}
種群詳細(xì)信息類(lèi)：
package edu.zsu.zouang.inheritence;
public class GenerationDetail {
private double averageFitness = 0.0;
private double maxFitness = 0.0;
private double minFitness = 0.0;
public double getAverageFitness() {
return averageFitness;
}
public void setAverageFitness(double averageFitness) {
this.averageFitness = averageFitness;
}
public double getMaxFitness() {
return maxFitness;
}
public void setMaxFitness(double maxFitness) {
this.maxFitness = maxFitness;
}
public double getMinFitness() {
return minFitness;
}
public void setMinFitness(double minFitness) {
this.minFitness = minFitness;
}
}
最后是主類(lèi)：
package edu.zsu.zouang.inheritence;
import java.util.ArrayList;
import java.util.List;
import edu.zsu.zouang.util.Randomizer;
public class GeneticAlgorithm {
private int generation; //進(jìn)化代數(shù)
private int population; //種群數(shù)量
private double crossoverPossibility; //繁殖概率
private double mutationPossibility; //變異概率
private FitnessCalculate calculator = new FunctionFitness(); //適應(yīng)函數(shù)計(jì)算
private List<Chromosome> clist = new ArrayList<Chromosome>();
private Randomizer random1; //隨機(jī)數(shù)生成器1,用于生成變異位和交配位
private Randomizer random2 = new Randomizer(0,1); //隨機(jī)數(shù)生成器2，用于生成0-1之間的概率
private GenerationDetail detail = new GenerationDetail();
public GeneticAlgorithm(int population, double sp, double cp, double mp,int length){
this.population = population;
this.crossoverPossibility = cp;
this.mutationPossibility = mp;
random1 = new Randomizer(0,length - 1);
generatePopulation(0,255,length); //用24位表示一組x,y,z的值
}
/** *//**
* 生成初始種群
* @param lower
* @param upper
* @param length
*/
private void generatePopulation(int lower, int upper, int length){
//隨機(jī)生成染色體
for(int i = 0; i < population; i ++){
clist.add(new Chromosome(lower,upper,length));
}
//計(jì)算染色體的適應(yīng)值
evaluate();
}
/** *//**
* 計(jì)算群體的適應(yīng)值
*/
private void evaluate(){
double sum = 0.0;
double min = Double.MAX_VALUE;
double max = Double.MIN_VALUE;
for(Chromosome c : clist){
double fitness = calculator.calculate(c.getChromo());
if(fitness > max){
max = fitness;
}
if(fitness < min){
min = fitness;
}
c.setFitness(fitness);
sum += fitness;
}
detail.setMaxFitness(max);
detail.setMinFitness(min);
detail.setAverageFitness(sum/population);
for(Chromosome c : clist){
c.setSelect((c.getFitness())/sum); //設(shè)置選擇概率
}
}
/** *//**
* 在后代中選擇新種群
*/
private void selectPopulation(){
List<Chromosome> tempList = new ArrayList<Chromosome>();
for(Chromosome c : clist){
long expectation = Math.round(c.getSelect() * population);
for(int i = 0; i < expectation; i ++){
tempList.add(c.clone());
}
}
//如果選擇種群數(shù)量大于種群規(guī)定數(shù)量，則淘汰適應(yīng)值最小的染色體
while(tempList.size() > population){
int location = 0;
double min = tempList.get(0).getFitness();
for(int i = 0 ; i < tempList.size(); i ++){
if(tempList.get(i).getFitness() < min){
location = i;
}
}
tempList.remove(location);
}
//如果選擇種群數(shù)量小于種群規(guī)定數(shù)量，則加入適應(yīng)值最大的染色體
while(tempList.size() < population){
int location = 0;
double max = tempList.get(0).getFitness();
for(int i = 0; i < tempList.size(); i++){
if(tempList.get(i).getFitness() > max){
location = i;
}
}
tempList.add(tempList.get(location).clone());
}
clist = tempList;
}
/** *//**
* 交配兩個(gè)染色體
* @param c1
* @param c2
* @param location
*/
private void crossover(Chromosome c1, Chromosome c2){
if(c1.getChromo().length != c2.getChromo().length){
throw new IllegalStateException("染色體長(zhǎng)度不同!");
}
//交換染色體上的基因
//隨機(jī)確定交配位
int location = random1.nextInteger();
for(int i = location ; i < c1.getChromo().length; i ++){
char temp;
temp = c1.getChromo()[i];
c1.getChromo()[i] = c2.getChromo()[i];
c2.getChromo()[i] = temp;
}
}
/** *//**
* 交配整個(gè)種群,完成一次進(jìn)化
*
*/
public void crossoverPopulation(){
for(int j = 0; j < population; j ++){
for(int i = 0; i < population - 1; i++){
double temp = random2.nextDouble();
if(temp < crossoverPossibility){//在交配概率之內(nèi)
crossover(clist.get(i), clist.get(i + 1));
}
}
double mutation = random2.nextDouble();
if(mutation < mutationPossibility){//在變異概率之內(nèi)
mutation(clist.get(j));
}
}
//重新計(jì)算群體適應(yīng)值
evaluate();
//重新選擇種群
selectPopulation();
generation ++;
}
//隨機(jī)變異一位
private void mutation(Chromosome ch){
int location = random1.nextInteger();
char c = ch.getChromo()[location];
if(c == '1'){
ch.getChromo()[location] = '0';
}else{
ch.getChromo()[location] = '1';
}
}
public void printDetail(){
System.out.println("/*****************************************");
System.out.println("* -----遺傳算法報(bào)告----- ");
System.out.println("* 當(dāng)前是第" + generation + "代");
System.out.println("* 當(dāng)前種群平均適應(yīng)值為: " + detail.getAverageFitness());
System.out.println("* 其中最大適應(yīng)值為:" + detail.getMaxFitness());
System.out.println("* 其中最小適應(yīng)值為:" + detail.getMinFitness());
System.out.println("*******************************************/");
}
public static void main(String[] args){
//種群數(shù)量：30
//選擇概率：0.0
//交配概率：0.9
//變異概率: 0.01
GeneticAlgorithm ga = new GeneticAlgorithm(30,0.0,0.9,0.01,24);
for(int i = 0; i < 5; i ++){
ga.crossoverPopulation();
}
ga.printDetail();
for(int j = 0; j < 25; j++){
ga.crossoverPopulation();
}
ga.printDetail();
for(int k = 0; k < 1000; k++){
ga.crossoverPopulation();
}
ga.printDetail();
}
}
輸出的結(jié)果是
/** *//*****************************************
* -----遺傳算法報(bào)告-----
* 當(dāng)前是第5代
* 當(dāng)前種群平均適應(yīng)值為: 7592451.0488077225
* 其中最大適應(yīng)值為:9031331.437029611
* 對(duì)應(yīng)最大適應(yīng)值的染色體為:111011101101010010111000
* 其中最小適應(yīng)值為:-1.2521097155031694E7
* 其中對(duì)應(yīng)最小適應(yīng)值的染色體為111011101101010011111011
*******************************************/
/** *//*****************************************
* -----遺傳算法報(bào)告-----
* 當(dāng)前是第30代
* 當(dāng)前種群平均適應(yīng)值為: 8785113.746617064
* 其中最大適應(yīng)值為:9836674.727850026
* 對(duì)應(yīng)最大適應(yīng)值的染色體為:111111101101010010111000
* 其中最小適應(yīng)值為:-1.1676031572464054E7
* 其中對(duì)應(yīng)最小適應(yīng)值的染色體為111011101101010011111000
*******************************************/
/** *//*****************************************
* -----遺傳算法報(bào)告-----
* 當(dāng)前是第1030代
* 當(dāng)前種群平均適應(yīng)值為: 8763072.724911185
* 其中最大適應(yīng)值為:9836674.727850026
* 對(duì)應(yīng)最大適應(yīng)值的染色體為:111111101101010010111000
* 其中最小適應(yīng)值為:-9580464.117842415
* 其中對(duì)應(yīng)最小適應(yīng)值的染色體為111101101101010010111000
*******************************************/
示例程序見(jiàn)：
http://www.aygfsteel.com/richardeee/archive/2007/04/29/114536.html