本文目录一览：
如何用Java实现遗传算法？
通过遗传算法走迷宫。虽然图1和图2均成功走出迷宫，但是图1比图2的路径长的多，且复杂，遗传算法可以计算出有多少种可能性，并选择其中最简洁的作为运算结果。
示例图1：
示例图2：
实现代码：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
/**
* 用遗传算法走迷宫
*
* @author Orisun
*
*/
public class GA {
int gene_len; // 基因长度
int chrom_len; // 染色体长度
int population; // 种群大小
double cross_ratio; // 交叉率
double muta_ratio; // 变异率
int iter_limit; // 最多进化的代数
Listboolean[] individuals; // 存储当代种群的染色体
Labyrinth labyrinth;
int width; //迷宫一行有多少个格子
int height; //迷宫有多少行
public class BI {
double fitness;
boolean[] indv;
public BI(double f, boolean[] ind) {
fitness = f;
indv = ind;
}
public double getFitness() {
return fitness;
}
public boolean[] getIndv() {
return indv;
}
}
ListBI best_individual; // 存储每一代中最优秀的个体
public GA(Labyrinth labyrinth) {
this.labyrinth=labyrinth;
this.width = labyrinth.map[0].length;
this.height = labyrinth.map.length;
chrom_len = 4 * (width+height);
gene_len = 2;
population = 20;
cross_ratio = 0.83;
muta_ratio = 0.002;
iter_limit = 300;
individuals = new ArrayListboolean[](population);
best_individual = new ArrayListBI(iter_limit);
}
public int getWidth() {
return width;
}
public void setWidth(int width) {
this.width = width;
}
public double getCross_ratio() {
return cross_ratio;
}
public ListBI getBest_individual() {
return best_individual;
}
public Labyrinth getLabyrinth() {
return labyrinth;
}
public void setLabyrinth(Labyrinth labyrinth) {
this.labyrinth = labyrinth;
}
public void setChrom_len(int chrom_len) {
this.chrom_len = chrom_len;
}
public void setPopulation(int population) {
this.population = population;
}
public void setCross_ratio(double cross_ratio) {
this.cross_ratio = cross_ratio;
}
public void setMuta_ratio(double muta_ratio) {
this.muta_ratio = muta_ratio;
}
public void setIter_limit(int iter_limit) {
this.iter_limit = iter_limit;
}
// 初始化种群
public void initPopulation() {
Random r = new Random(System.currentTimeMillis());
for (int i = 0; i population; i++) {
int len = gene_len * chrom_len;
boolean[] ind = new boolean[len];
for (int j = 0; j len; j++)
ind[j] = r.nextBoolean();
individuals.add(ind);
}
}
// 交叉
public void cross(boolean[] arr1, boolean[] arr2) {
Random r = new Random(System.currentTimeMillis());
int length = arr1.length;
int slice = 0;
do {
slice = r.nextInt(length);
} while (slice == 0);
if (slice length / 2) {
for (int i = 0; i slice; i++) {
boolean tmp = arr1[i];
arr1[i] = arr2[i];
arr2[i] = tmp;
}
} else {
for (int i = slice; i length; i++) {
boolean tmp = arr1[i];
arr1[i] = arr2[i];
arr2[i] = tmp;
}
}
}
// 变异
public void mutation(boolean[] individual) {
int length = individual.length;
Random r = new Random(System.currentTimeMillis());
individual[r.nextInt(length)] ^= false;
}
// 轮盘法选择下一代,并返回当代最高的适应度值
public double selection() {
boolean[][] next_generation = new boolean[population][]; // 下一代
int length = gene_len * chrom_len;
for (int i = 0; i population; i++)
next_generation[i] = new boolean[length];
double[] cumulation = new double[population];
int best_index = 0;
double max_fitness = getFitness(individuals.get(best_index));
cumulation[0] = max_fitness;
for (int i = 1; i population; i++) {
double fit = getFitness(individuals.get(i));
cumulation[i] = cumulation[i - 1] + fit;
// 寻找当代的最优个体
if (fit max_fitness) {
best_index = i;
max_fitness = fit;
}
}
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i population; i++)
next_generation[i] = individuals.get(findByHalf(cumulation,
rand.nextDouble() * cumulation[population - 1]));
// 把当代的最优个体及其适应度放到best_individual中
BI bi = new BI(max_fitness, individuals.get(best_index));
// printPath(individuals.get(best_index));
//System.out.println(max_fitness);
best_individual.add(bi);
// 新一代作为当前代
for (int i = 0; i population; i++)
individuals.set(i, next_generation[i]);
return max_fitness;
}
// 折半查找
public int findByHalf(double[] arr, double find) {
if (find 0 || find == 0 || find arr[arr.length - 1])
return -1;
int min = 0;
int max = arr.length - 1;
int medium = min;
do {
if (medium == (min + max) / 2)
break;
medium = (min + max) / 2;
if (arr[medium] find)
min = medium;
else if (arr[medium] find)
max = medium;
else
return medium;
} while (min max);
return max;
}
// 计算适应度
public double getFitness(boolean[] individual) {
int length = individual.length;
// 记录当前的位置,入口点是（1,0）
int x = 1;
int y = 0;
// 根据染色体中基因的指导向前走
for (int i = 0; i length; i++) {
boolean b1 = individual[i];
boolean b2 = individual[++i];
// 00向左走
if (b1 == false b2 == false) {
if (x 0 labyrinth.map[y][x - 1] == true) {
x--;
}
}
// 01向右走
else if (b1 == false b2 == true) {
if (x + 1 width labyrinth.map[y][x + 1] == true) {
x++;
}
}
// 10向上走
else if (b1 == true b2 == false) {
if (y 0 labyrinth.map[y - 1][x] == true) {
y--;
}
}
// 11向下走
else if (b1 == true b2 == true) {
if (y + 1 height labyrinth.map[y + 1][x] == true) {
y++;
}
}
}
int n = Math.abs(x - labyrinth.x_end) + Math.abs(y -labyrinth.y_end) + 1;
// if(n==1)
// printPath(individual);
return 1.0 / n;
}
// 运行遗传算法
public boolean run() {
// 初始化种群
initPopulation();
Random rand = new Random(System.currentTimeMillis());
boolean success = false;
while (iter_limit-- 0) {
// 打乱种群的顺序
Collections.shuffle(individuals);
for (int i = 0; i population - 1; i += 2) {
// 交叉
if (rand.nextDouble() cross_ratio) {
cross(individuals.get(i), individuals.get(i + 1));
}
// 变异
if (rand.nextDouble() muta_ratio) {
mutation(individuals.get(i));
}
}
// 种群更替
if (selection() == 1) {
success = true;
break;
}
}
return success;
}
// public static void main(String[] args) {
// GA ga = new GA(8, 8);
// if (!ga.run()) {
// System.out.println("没有找到走出迷宫的路径.");
// } else {
// int gen = ga.best_individual.size();
// boolean[] individual = ga.best_individual.get(gen - 1).indv;
// System.out.println(ga.getPath(individual));
// }
// }
// 根据染色体打印走法
public String getPath(boolean[] individual) {
int length = individual.length;
int x = 1;
int y = 0;
LinkedListString stack=new LinkedListString();
for (int i = 0; i length; i++) {
boolean b1 = individual[i];
boolean b2 = individual[++i];
if (b1 == false b2 == false) {
if (x 0 labyrinth.map[y][x - 1] == true) {
x--;
if(!stack.isEmpty() stack.peek()=="右")
stack.poll();
else
stack.push("左");
}
} else if (b1 == false b2 == true) {
if (x + 1 width labyrinth.map[y][x + 1] == true) {
x++;
if(!stack.isEmpty() stack.peek()=="左")
stack.poll();
else
stack.push("右");
}
} else if (b1 == true b2 == false) {
if (y 0 labyrinth.map[y - 1][x] == true) {
y--;
if(!stack.isEmpty() stack.peek()=="下")
stack.poll();
else
stack.push("上");
}
} else if (b1 == true b2 == true) {
if (y + 1 height labyrinth.map[y + 1][x] == true) {
y++;
if(!stack.isEmpty() stack.peek()=="上")
stack.poll();
else
stack.push("下");
}
}
}
StringBuilder sb=new StringBuilder(length/4);
IteratorString iter=stack.descendingIterator();
while(iter.hasNext())
sb.append(iter.next());
return sb.toString();
}
}
遗传算法
例如：[1,2,3]，[1,3,2]，[3,2,1]均是函数 3x+4y+5z100 的可行解（代进去成立即为可行解），那么这些可行解在遗传算法中均称为“染色体”。可行解由 3 个元素构成，每个元素都称为染色体的一个基因。
遗传算法在运行过程中会进行 N 次迭代，每次迭代都会生成若干条染色体。适应度函数会给本次迭代中生成的所有染色体打个分，来评判这些染色体的适应度，然后将适应度低的染色体淘汰，只保留适应度高的染色体，从而讲过若干次迭代后染色体的质量将越来越好。
遗传算法每次迭代会生成 N 条染色体，在遗传算法中一次迭代被称为一次进化。每次进化新的染色体生成的方法——交叉。
每一次进化完成后，都要计算每一条染色体的适应度+适应度概率。在交叉过程中就需要根据这个概率来选择父母染色体。适应度高的染色体被选中的概率越高。（这就是遗传算法能够保留优良基因的原因）
交叉能保证每次进化留下优良的基因，但它仅仅是对原有的结果集进行选择，基因还是那么几个，只不过交换了它们的顺序。这只能保证 N 次进化后，计算结果更接近于局部最优解，而永远没办法达到全局最优解（？？？？？），为了解决这个问题，需引入变异。
假设每次进化都需要生成 N 条染色体，那么每次进化中，通过交叉方式需要生成 N-M 条，剩余的 M 条染色体通过复制上一代适应度最高的 M 条染色体而来。
本文的目标是使所有任务的总处理时间最少，时间越短适应度越大。适应度 = 1 / 所有任务的总处理时间
将任务从 0 开始编号，用一个一维数组存储每个任务的时长
tasks[i] ：表第 i 个任务的长度。
第 0 个任务的长度为 2；
第 1 个任务的长度为 4；
第 2 个任务的长度为 6；
第 3 个任务的长度为 8；
将处理器节点从 0 开始编号，用一个一维数组存储每个处理器的处理速度（单位时间内可处理的长度）
nodes[i] 表第 i 个节点的处理速度。
第 0 个节点的处理速度为 2；
第 1 个节点的处理速度为 1。
timeMatrix[i][j] 表第 i 个任务在第 j 个节点上处理的话，所需处理时间。
一个可行解就是一个染色体，就是一个一维数组
chromosome[i]=j 表将第 i 个任务分配到节点 j 上处理（任务编号从 0 开始；节点编号从 0 开始）
将任务 0 分配给 3 号节点处理；
将任务 1 分配给 2 号节点处理；
将任务 2 分配给 1 号节点处理；
将任务 3 分配给 0 号节点处理。
记录本次进化生成的 N 条染色体的适应度，将染色体从 0 开始编号。
adaptablility[i] 表第 i 个染色体的适应度
selectionProbability[i] 表第 i 个染色体的适应度概率，所有染色体的适应度概率和为 1 。
java中PriorityQueue优先级队列使用方法
第 2 次迭代结果
第 100 次迭代结果
《Java遗传算法编程》pdf下载在线阅读全文，求百度网盘云资源
《Java遗传算法编程》百度网盘pdf最新全集下载:
链接:
?pwd=xv3v 提取码: xv3v
简介：本书简单、直接地介绍了遗传算法，并且针对所讨论的示例问题，给出了Java代码的算法实现。全书分为6章。第1章简单介绍了人工智能和生物进化的知识背景，这也是遗传算法的历史知识背景。第2章给出了一个基本遗传算法的实现；第4章和第5章，分别针对机器人控制器、旅行商问题、排课问题展开分析和讨论，并给出了算法实现。在这些章的末尾，还给出了一些练习供读者深入学习和实践。第6章专门讨论了各种算法的优化问题。
java实验 遗传算法
你好，我以前从csdn上下过一个源代码，不过没试过怎么用，给你参考一下：
import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.JTextField;
/**
* 编写者: 赖志环
* 标准遗传算法求解函数
* 编写日期: 2007-12-2
*/
class Best {
public int generations; //最佳适应值代号
public String str; //最佳染色体
public double fitness; //最佳适应值
}
public class SGAFrame extends JFrame {
private JTextArea textArea;
private String str = "";
private Best best = null; //最佳染色体
private String[] ipop = new String[10]; //染色体
private int gernation = 0; //染色体代号
public static final int GENE = 22; //基因数
/**
* Launch the application
* @param args
*/
public static void main(String args[]) {
try {
SGAFrame frame = new SGAFrame();
frame.setVisible(true);
} catch (Exception e) {
e.printStackTrace();
}
}
/**
* Create the frame
*/
public SGAFrame() {
super();
this.ipop = inialPops();
getContentPane().setLayout(null);
setBounds(100, 100, 461, 277);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
final JLabel label = new JLabel();
label.setText("X的区间:");
label.setBounds(23, 10, 88, 15);
getContentPane().add(label);
final JLabel label_1 = new JLabel();
label_1.setText("[-255,255]");
label_1.setBounds(92, 10, 84, 15);
getContentPane().add(label_1);
final JButton button = new JButton();
button.addActionListener(new ActionListener() {
public void actionPerformed(final ActionEvent e) {
SGAFrame s = new SGAFrame();
str = str + s.process() + "n";
textArea.setText(str);
}
});
button.setText("求最小值");
button.setBounds(323, 27, 99, 23);
getContentPane().add(button);
final JLabel label_2 = new JLabel();
label_2.setText("利用标准遗传算法求解函数f(x)=(x-5)*(x-5)的最小值:");
label_2.setBounds(23, 31, 318, 15);
getContentPane().add(label_2);
final JPanel panel = new JPanel();
panel.setLayout(new BorderLayout());
panel.setBounds(23, 65, 399, 164);
getContentPane().add(panel);
final JScrollPane scrollPane = new JScrollPane();
panel.add(scrollPane, BorderLayout.CENTER);
textArea = new JTextArea();
scrollPane.setViewportView(textArea);
//
}
/**
* 初始化一条染色体（用二进制字符串表示）
* @return 一条染色体
*/
private String inialPop() {
String res = "";
for (int i = 0; i GENE; i++) {
if (Math.random() 0.5) {
res += "0";
} else {
res += "1";
}
}
return res;
}
/**
* 初始化一组染色体
* @return 染色体组
*/
private String[] inialPops() {
String[] ipop = new String[10];
for (int i = 0; i 10; i++) {
ipop[i] = inialPop();
}
return ipop;
}
/**
* 将染色体转换成x的值
* @param str 染色体
* @return 染色体的适应值
*/
private double calculatefitnessvalue(String str) {
int b = Integer.parseInt(str, 2);
//String str1 = "" + "/n";
double x = -255 + b * (255 - (-255)) / (Math.pow(2, GENE) - 1);
//System.out.println("X = " + x);
double fitness = -(x - 5) * (x - 5);
//System.out.println("f(x)=" + fitness);
//str1 = str1 + "X=" + x + "/n"
//+ "f(x)=" + "fitness" + "/n";
//textArea.setText(str1);
return fitness;
}
/**
* 计算群体上每个个体的适应度值;
* 按由个体适应度值所决定的某个规则选择将进入下一代的个体;
*/
private void select() {
double evals[] = new double[10]; // 所有染色体适应值
double p[] = new double[10]; // 各染色体选择概率
double q[] = new double[10]; // 累计概率
double F = 0; // 累计适应值总和
for (int i = 0; i 10; i++) {
evals[i] = calculatefitnessvalue(ipop[i]);
if (best == null) {
best = new Best();
best.fitness = evals[i];
best.generations = 0;
best.str = ipop[i];
} else {
if (evals[i] best.fitness) // 最好的记录下来
{
best.fitness = evals[i];
best.generations = gernation;
best.str = ipop[i];
}
}
F = F + evals[i]; // 所有染色体适应值总和
}
for (int i = 0; i 10; i++) {
p[i] = evals[i] / F;
if (i == 0)
q[i] = p[i];
else {
q[i] = q[i - 1] + p[i];
}
}
for (int i = 0; i 10; i++) {
double r = Math.random();
if (r = q[0]) {
ipop[i] = ipop[0];
} else {
for (int j = 1; j 10; j++) {
if (r q[j]) {
ipop[i] = ipop[j];
break;
}
}
}
}
}
/**
* 交叉操作
* 交叉率为25%，平均为25%的染色体进行交叉
*/
private void cross() {
String temp1, temp2;
for (int i = 0; i 10; i++) {
if (Math.random() 0.25) {
double r = Math.random();
int pos = (int) (Math.round(r * 1000)) % GENE;
if (pos == 0) {
pos = 1;
}
temp1 = ipop[i].substring(0, pos)
+ ipop[(i + 1) % 10].substring(pos);
temp2 = ipop[(i + 1) % 10].substring(0, pos)
+ ipop[i].substring(pos);
ipop[i] = temp1;
ipop[(i + 1) / 10] = temp2;
}
}
}
/**
* 基因突变操作
* 1%基因变异m*pop_size 共180个基因，为了使每个基因都有相同机会发生变异,
* 需要产生[1--180]上均匀分布的
*/
private void mutation() {
for (int i = 0; i 4; i++) {
int num = (int) (Math.random() * GENE * 10 + 1);
int chromosomeNum = (int) (num / GENE) + 1; // 染色体号
int mutationNum = num - (chromosomeNum - 1) * GENE; // 基因号
if (mutationNum == 0)
mutationNum = 1;
chromosomeNum = chromosomeNum - 1;
if (chromosomeNum = 10)
chromosomeNum = 9;
//System.out.println("变异前" + ipop[chromosomeNum]);
String temp;
if (ipop[chromosomeNum].charAt(mutationNum - 1) == '0') {
if (mutationNum == 1) {
temp = "1" + ipop[chromosomeNum].substring
(mutationNum);
} else {
if (mutationNum != GENE) {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "1" + ipop
[chromosomeNum].substring(mutationNum);
} else {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "1";
}
}
} else {
if (mutationNum == 1) {
temp = "0" + ipop[chromosomeNum].substring
(mutationNum);
} else {
if (mutationNum != GENE) {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "0" + ipop
[chromosomeNum].substring(mutationNum);
} else {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "1";
}
}
}
ipop[chromosomeNum] = temp;
//System.out.println("变异后" + ipop[chromosomeNum]);
}
}
/**
* 执行遗传算法
*/
public String process() {
String str = "";
for (int i = 0; i 10000; i++) {
this.select();
this.cross();
this.mutation();
gernation = i;
}
str = "最小值" + best.fitness + ",第" + best.generations + "个染色体";
return str;
}
}