遗传算法的java实现

⑴ 《java遗传算法编程》pdf下载在线阅读全文，求百度网盘云资源

《Java遗传算法编程》网络网盘pdf最新全集下载:
链接: https://pan..com/s/1l6_14X1Yhcgv8kYwHqyY2g

⑵ 遗传算法求最短路径

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#include<string>
using namespace std;

#define OVERFLOW -2
#define OK 1
#define ERROR 0

#define INFINITY 200//最大值
#define MAX_VERTEX_NUM 20//最大顶点个数

typedef char VertexType;//定义为char类型

//以下是全局变量,用于保存弗洛伊德算法的路径和长度
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径长度
int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径标记
//以下是全局变量,用于保存迪杰斯特拉算法的路径和长度
int Distance[MAX_VERTEX_NUM];
VertexType former[MAX_VERTEX_NUM];//终点的前一个顶点
bool final[MAX_VERTEX_NUM];//记录顶点是否在V-S中

typedef struct ArcCell
{
int adj; //顶点关系类型
int weight; //该弧相关信息的指针,在此记录为权值
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum; //顶点数
int arcnum; //弧数
}MGraph;

void InitialMGraph(MGraph &G)//初始化
{
G.arcnum=G.vexnum=0; //初始化边数跟顶点数都为零
for(int i=0;i<MAX_VERTEX_NUM;i++)
for(int j=0;j<MAX_VERTEX_NUM;j++)
{
if(i==j)
G.arcs[i][j].weight=0;
else
G.arcs[i][j].weight=INFINITY; //初始化为200,以200认为是无穷大
}
}

void InsertVex(MGraph &G,VertexType v)//插入顶点
{
if(G.vexnum<=MAX_VERTEX_NUM)
G.vexs[G.vexnum++]=v;
}

void InsertArc(MGraph &G,VertexType v1,VertexType v2)//插入边
{
int m,n;
G.arcnum++;
for(int k=0;k<G.vexnum;k++)
{
if(G.vexs[k]==v1)
m=k;
if(G.vexs[k]==v2)
n=k;
}
//插入
ArcCell A;
cout<<"请输入权值:";
cin>>A.weight;
G.arcs[m][n].weight=A.weight;
}

//迪杰斯特拉最短路径,假设始点就存储在数组中的第一个
void ShortestPath_DIJ(MGraph G,int v0)
{
//初始化距离
for(int v=0;v<G.vexnum;++v)
{
final[v]=false;
Distance[v]=G.arcs[v0][v].weight;
if(Distance[v]<INFINITY&&Distance[v]!=0)
{
former[v]=G.vexs[v0];
}
else
former[v]='#';
}
final[v0]=true;
former[v0]=G.vexs[v0];
for(int i=1;i<G.vexnum;++i)//剩余的G.vexnum-1个顶点
{
int w;
int min=INFINITY;
int v=-1;
for(w=0;w<G.vexnum;++w)
{
if(!final[w]&&Distance[w]<min)
{
v=w;
min=Distance[w];
}
}
if(v!=-1)
{
final[v]=true;//将离顶点V0最近的顶点v加入S集合中
for(w=0;w<G.vexnum;++w)//更新当前的最短路径及距离
{
if(!final[w]&&(min+G.arcs[v][w].weight<Distance[w])&&G.arcs[v][w].weight<INFINITY)
{
Distance[w]=min+G.arcs[v][w].weight;
former[w]=G.vexs[v];
}
}
}
}
}
//输出迪杰斯特拉中的最短路径
void output_ShortestPath_DIJ(MGraph G,int v0)
{
int i;
for(i=1;i<G.vexnum;i++)
{
cout<<G.vexs[v0]<<"->"<<G.vexs[i]<<":";
if(Distance[i]!=INFINITY)
{
cout<<"最短路径长度为:"<<Distance[i]<<" 最短路径的前一个顶点为:"<<former[i];
cout<<endl;
}
else
cout<<"此两顶点之间不存在路径"<<endl;
}
}
//弗洛伊德最短路径
void shortestPath_FLOYD(MGraph G)
{
for(int v=0;v<G.vexnum;++v)
{
for(int w=0;w<G.vexnum;++w)
{
D[v][w]=G.arcs[v][w].weight;
for (int k=0;k< G.vexnum;k++)
P[v][w][k]=-1;
if(D[v][w]<INFINITY) //从v到w有直接路径
P[v][w][v]=w;
}
}
for(int k=0;k<G.vexnum;++k)
{
for(int v=0;v<G.vexnum;v++)
for(int w=0;w<G.vexnum;++w)
if(D[v][w]>D[v][k]+D[k][w])
{
D[v][w]=D[v][k]+D[k][w];
for(int i=0;i<G.vexnum;i++)
{
if(P[v][k][i]!=-1)//原来存了顶点
P[v][w][i]=P[v][k][i];
else
P[v][w][i]=P[k][w][i];
}
}
}
}
//输出弗洛伊德中的最短路径
void output_shortestPath_FLOYD(MGraph G)
{
for(int i=0;i<G.vexnum;++i)
{
for(int j=0;j<G.vexnum;++j)
{
if(i!=j)//自己不能到达自己
{
cout<<G.vexs[i]<<"->"<<G.vexs[j]<<":";
if(D[i][j]==INFINITY)
{
cout<<"此两顶点之间不存在路径"<<endl;
}
else
{
cout<<"最短路径长度为:"<<" "<<D[i][j]<<" ";
cout<<"最短路径为:";
cout<<G.vexs[i];
for(int k=i;k!=-1;k=P[i][j][k])
{
if(k!=i)
cout<<G.vexs[k];
}
cout<<endl;
}
}
}
}
}

int main()
{
int num1;//顶点个数
int num2;//弧个数
cout<<"请输入顶点个数:";
cin>>num1;
cout<<"请输入弧个数:";
cin>>num2;
VertexType v;
MGraph G;
InitialMGraph(G);
cout<<"请输入顶点的信息:"<<endl;
for(int i=0;i<num1;++i)
{
cin>>v;;
InsertVex(G,v);
}
VertexType v1,v2;
for(int j=0;j<num2;++j)
{
cout<<"请输入两个结点数据来表示的边:";
cin>>v1>>v2;
InsertArc(G,v1,v2);
}
ShortestPath_DIJ(G,0);
cout<<"迪杰斯特拉中的最短路径如下:"<<endl;
output_ShortestPath_DIJ(G,0);
cout<<endl<<endl;
shortestPath_FLOYD(G);
cout<<"弗洛伊德中的最短路径如下:"<<endl;
output_shortestPath_FLOYD(G);
return 0;
}

⑶ 使用java来实现在智能组卷中的遗传算法（急急急）

题目好像是让你做个增强版的List ，简单的都实现了 程序架子大概是这样，排序查找什么的网络搜下 算法很多，套着每样写个方法就行了，测试就在main‘方法里写

publicclassMyList{
privateString[]arr;
privateintcount;
publicMyList(intcount){
arr=newString[count];
this.count=count;
}
publicMyList(int[]intArr){
arr=newString[intArr.length];
this.count=intArr.length;
for(inti=0;i<intArr.length;i++){
arr[i]=intArr[i]+"";
}
}

publicMyList(String[]stringArr){
arr=stringArr;
this.count=stringArr.length;
}
publicintgetLength(){
returncount;
}
//清空容器内的数组。
publicvoidclearAll(){
arr=newString[count];
}
//通过给定元素下标来删除某一元素
publicvoidremoveBySeqn(intseqn){
if(seqn>=0&&seqn<count){
arr[seqn]=null;
}
}
publicstaticvoidmain(String[]args){
MyListlist=newMyList(40);
MyListlist1=newMyList({3,2,125,56,123});
MyListlist2=newMyList({"123",""ad});
list2.removeBySeqn(0);
list1.clearAll();
}
}

⑷ 遗传算法^[1，]

遗传算法，又称基因算法(Genetic Algorithm，简称GA)，也是一种启发式蒙特卡洛优化算法。遗传算法最早是由Holland(1975)提出，它模拟了生物适者生存、优胜劣汰的进化过程，具有不依赖于初始模型的选择、不容易陷入局部极小、在反演过程中不用计算偏导数矩阵等优点。遗传算法最早由Stoffa和Sen(1991)用于地震波的一维反演，之后在地球物理资料的非线性反演中得到广泛的应用。GA算法对模型群体进行追踪、搜索，即模型状态通过模型群体传送，具有比模拟退火法更大、更复杂的“记忆”，潜力更大。

遗传算法在反演中的基本思路和过程是:

(1)将生物体看成模型，模型参数看成染色体，有多少个模型的参数就有多少个染色体。对每个模型的参数(染色体)用二进制进行编码，这个编码就是基因。

(2)随机生成一个模型群体(相当于生物的种群)，然后在模型群体中进行繁殖，通过母本的选择、交换和变异等遗传操作产生下一代，然后保留较好基因，淘汰较差基因。

(3)通过一代一代的繁殖优胜劣汰的进化过程，最后所剩下的种群基本上都是最优的基因，种群趋于一致。所谓群体“一致”，即群体目标函数的方差或标准差很小，或者群体目标函数的均值接近于极值(可能是极大值或极小值)，从而获得非线性反演问题所对应的最优解或近似最优解。

下面以一个实例来简述遗传算法的基本过程。

[例1]设m是正整数，且0≤m≤127，求方程φ(m)=m²的极大值。

这个例子极为简单，只有一个模型参数，因此只有一条染色体，目标函数的极值是极大值(此例子来自阮百尧课件)。遗传算法通过以下7个步骤来实现:

(1)模型参数二进制编码。

每个模型参数就是一条染色体，把十进制的模型参数表示为二进制，这就是基因。首先确定二进制码的长度(基因的长度):

2^N=[m_max(i)-m_min(i)]/Δm(i) (8.20)

其中:N为第i条染色体基因的长度(也就是第i个模型参数的二进制码位数);[m_min(i)，m_max(i)]为第i个模型参数的取值范围;Δm(i)为第i个模型参数的分辨率。这样就把模型参数离散化了，它只能按Δm(i)的整数倍变化。基因的长度按下式计算:

地球物理反演教程

其中:c为实数;N为基因长度，是整数;int[ ]为取整函数。上式表示如果c不是整数，那么基因长度N就是对c取整后加1，这样保证最小分辨率。

基因的编码按下式进行:

地球物理反演教程

其中:式(8.22)是编码公式;k为基因编码的十进制数，是整数;int[ ]为取整函数。把k转化为二进制就是基因的编码。解码是按照式(8.23)进行的。首先把一个基因的二进制编码转化为十进制数k，然后按式(8.23)可以计算出第i个模型参数m(i)的十进制值。

例如:电阻率参数ρ(1)，它的变化范围为10~5000Ω·m，分辨率为2Ω·m，设当前参数ρ(1)=133Ω·m，按式(8.21)计算得

c=11.28482，N=12

所以二进制基因长度为13位。

利用式(8.22)计算基因编码k的十进制数:

k=int[(133-10)/2]=61

把它转化为二进制数为:000000111101。所以ρ(1)=133 的二进制基因编码为:000000111101。

解码过程就是把二进制基因编码变为十进制数k后用式(8.23)计算:

ρ(1)=10+61×2=132(Ω·m)

注意:基因编码并不是直接把电阻率值变为二进制。此外，133这个值在基因里不会出现，因为分辨率是2，所以表示为最接近的132。

对于[例1]问题来说，选分辨率为1，0~127用二进制编码需7位。

(2)产生初始模型种群。

生物繁殖进化需要一定数量的生物体种群，因此遗传算法开始时需要一定数量的初始模型。为保证基因的多样性，随机产生大量的初始模型作为初始种群，按照上面的编码方式进行编码。个体在模型空间中应分布均匀，最好是模型空间各代表区域均有成员。初始模型群体大，有利于搜索，但太大会增加计算量。

为保证算法收敛，在初始模型群体中，有时候应增加各位都为0和都为1的成员。遗传算法就是在这个初始模型种群的基础上进行繁殖，进化求解的。

对于[例1]问题来说，模型空间是0~127个数字，这样初始种群最多具有128个个体。为了简单，随机选择4个个体作为初始种群。初始种群的编码、目标函数值见表8.1。

表8.1 初始种群编码表

(3)模型选择。

为了生成新一代模型，需要选择较优的个体进行配对。生物进化按照自然选择、优胜劣汰的准则进行。对应地，遗传算法按照一定的准则来选择母本(两个)，然后进行配对繁殖下一代模型，这个选择称为模型选择。模型配对最基本的方法是随机采样，用各模型的目标函数值对所有模型目标函数的平均值的比值定义繁殖概率，即

地球物理反演教程

其中:p(m_i)为繁殖概率;φ(m_i)为第i个模型的目标函数;φ_AVG为目标函数的平均值。对于极小化问题来说，规定目标函数值高于平均值的不传代;对于极大化问题来说，反之即可。

就[例1]来说，要求目标函数取极大值，所以规定目标函数小于平均值的模型不传代，大于它的可以传代。对第一代，为了防止基因丢失，可先不舍去繁殖概率小的模型，让它与概率大的模型配对。如:本例中70与56配对，101与15配对产生子代，见表8.2。

表8.2 基因交换表

(4)基因交换。

将配对的两个亲本模型的部分染色体相互交换，其中交换点可随机选择，形成两个新的子代(见表8.2)。两个染色体遗传基因的交换过程是遗传算法的“繁殖”过程，是母本的重组过程。

为了使染色体的基因交换比较彻底，Stoffa等人提出了一个交换概率p_x来控制选择操作的效果。如果p_x的值较小，那么交换点的位置就比较靠低位，这时的交换操作基本是低位交换，交换前后模型的染色体变化不是太大。如果p_x的值较大，那么交换点的位置就比较靠高位，此时的交换操作可以在较大的染色体空间进行，交换前后模型数值变化可以很大。

在[例1]中:15、101和56、70作为母本通过交换繁殖出子代5、6、111、120。所选择的基因交换位置见表8.2。有下划线的，是要交换的基因位置。

(5)更新。

母本模型和子本模型如何选择保留一定数量作为新的母本，就是模型更新。不同的策略会导致不同的结果。一般而言，若产生的新一代模型较好，则选择新一代模型而淘汰上一代模型。否则，则必须根据一定的更新概率p_u来选择上一代模型来取代新一代中某些较劣的模型。

经过更新以后，繁殖时对子代再进行优胜劣汰的选择。对于极大值问题，大于目标函数平均值的子代可以繁殖，小于目标函数平均值的子代不能繁殖。由于新的种群能繁殖的个体数量减小了，所以要多繁殖几次，维持种群个体的数量保持平衡。

在[例1]中，子代较好，所以完全淘汰上一代模型，完全用子代作为新的母本。选择子代目标函数最大的两个模型进行繁殖，分别是111、120。

(6)基因变异。

在新的配对好的母本中，按一定比例随机选择模型进行变异，变异操作就是模拟自然界中的环境因素，就是按比较小的变异概率p_m将染色体某位或某几位的基因发生突变(即将0变为1或将1变为0)。

变异操作的作用是使原来的模型发生某些变化，从而成为新的个体。这样可使群体增加多样性。变异操作在遗传算法中也起着至关重要的作用。实际上，由于搜索空间的性质和初始模型群体的优劣，遗传算法搜索过程中往往会出现所谓的“早熟收敛”现象，即在进化过程中早期陷入局部解而中止进化。采用合适的变异策略可提高群体中个体的多样性，从而防止这种现象的出现，有助于模型跳出局部极值。表8.3为[例1]的基因变异繁殖表。

表8.3 基因变异繁殖表

在[例1]中，用111、120分别繁殖两次，形成4个子代，维持种群数量平衡。随机选择120进行变异，变异的位数也是随机的。这里把它的第2位进行变异，即从1变为0，繁殖后形成子代为:70、110、121、127。可以看出新的子代比初始种群要好得多，其中甚至已经出现了最优解。如果对于地球物理的极小值问题，我们可以预先设置一个拟合精度，只要在种群中出现一个达到拟合精度的模型就可以终止反演了。

(7)收敛。

重复(3)~(6)的步骤，模型群体经多次选择、交换、更新、变异后，种群个体数量大小不变，模型目标函数平均值趋于稳定，最后聚集在模型空间中一个小范围内，则找到了全局极值对应的解，使目标函数最大或最小的模型就是全局最优模型。

对于具有多解性的地球物理反演问题来说，通过这一步有可能找到满足拟合精度的多个模型，对于实际反演解释、推断具有较高的指导意义。

遗传算法中的各种概率包括交换概率px、变异概率p_m以及更新概率p_u，这些参数的选择与设定目前尚无统一的理论指导，多数都视具体问题而定。Stoffa等(1991)的研究表明，适中的交换概率(p_x≈0.6)、较小的变异概率(p_m≈0.01)和较大的更新概率(p_u≈0.9)，遗传算法的性能较优。

与模拟退火反算法相同，遗传算法与传统的线性反演方法相比，该方法具有:不依赖初始模型的选择、能寻找全局最小点而不陷入局部极小、在反演过程中不用计算雅克比偏导数矩阵等优点。另外，遗传算法具有并行性，随着并行计算和集群式计算机技术的发展，该算法将会得到越来越广泛的研究与应用。

但是遗传算法作为类蒙特卡洛算法同样需要进行大量的正演计算，种群个体数量越大，繁衍代数越多，则计算量越大。所以和前面的最小二乘法相比，速度不是它的优势。

⑸ 用JAVA实现遗传算法求最小值的问题，一直报错，如下： 应该是越界抛的异常，如何解决呢

具体遗传算法我没研究过，但是这个异常是数组下标越界引起的，数组里没有数据，你去索引了第一个，肯定是哪里不细心了，如果逻辑没问题的话，在这一行(GeneticAlgorithmMin.java:102)加个判断，数组长度为0就不索引，这样就不会报错。 不过我估计涉及到逻辑性的其他地方了，就算不报错，程序也会有逻辑性问题，你给的资料不够，我尽力了

⑹ 急求 遗传算法 java程序

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;
}

}

⑺ 如何用遗传算法实现多变量的最优化问题

将多个变量的数值编码编排进去，进行组合。

⑻ 优化算法笔记（六）遗传算法

遗传算法(Genetic Algorithms，GA)是一种模拟自然中生物的遗传、进化以适应环境的智能算法。由于其算法流程简单，参数较少优化速度较快，效果较好，在图像处理、函数优化、信号处理、模式识别等领域有着广泛的应用。
在遗传算法（GA）中，每一个待求问题的候选解被抽象成为种群中一个个体的基因。种群中个体基因的好坏由表示个体基因的候选解在待求问题中的所的得值来评判。种群中的个体通过与其他个体交叉产生下一代，每一代中个体均只进行一次交叉。两个进行交叉的个体有一定几率交换一个或者多个对应位的基因来产生新的后代。每个后代都有一定的概率发生变异。发生变异的个体的某一位或某几位基因会变异成其他值。最终将以个体的适应度值为概率选取个体保留至下一代。

遗传算法启发于生物的繁殖与dna的重组，本次的主角选什么呢？还是根据大家熟悉的孟德尔遗传规律选豌豆吧，选动物的话又会有人疑车，还是植物比较好，本次的主角就是它了。

遗传算法包含三个操作（算子）：交叉，变异和选择操作。下面我们将详细介绍这三个操作。
大多数生物的遗传信息都储存在DNA，一种双螺旋结构的复杂有机化合物。其含氮碱基为腺嘌呤、鸟嘌呤、胞嘧啶及胸腺嘧啶。

表格中表示了一个有10个基因的个体，它们每一个基因的值为0或者1。

生物的有性生殖一般伴随着基因的重组。遗传算法中父辈和母辈个体产生子代个体的过程称为交叉。

表中给出了两个豌豆的基因，它们均有10个等位基因（即编号相同的基因）。
遗传算法的交叉过程会在两个个体中随机选择1位或者n位基因进行交叉，即这两个个体交换等位基因。
如，A豌豆和B豌豆在第6位基因上进行交叉，则其结果如下

当两个个体交叉的等位基因相同时，交叉过程也有可能没有产生新的个体，如交叉A豌豆和B豌豆的第2位基因时，交叉操作并没有产生新的基因。

一般的会给群体设定一个交叉率，crossRate，表示会在群体中选取一定比例的个体进行交叉，交叉率相对较大，一般取值为0.8。

基因的变异是生物进化的一个主要因素。
遗传算法中变异操作相对简单，只需要将一个随机位基因的值修改就行了，因为其值只为0或1，那么当基因为0时，变异操作会将其值设为1，当基因值为1时，变异操作会将其值设为0。

上图表示了A豌豆第3位基因变异后的基因编码。
与交叉率相似，变异操作也有变异率，alterRate，但是变异率会远低于交叉率，否则会产生大量的随机基因。一般变异率为0.05。

选择操作是遗传算法中的一个关键操作，它的主要作用就是根据一定的策略随机选择个体保留至下一代。适应度越优的个体被保留至下一代的概率越大。
实现上，我们经常使用“轮盘赌”来随机选择保留下哪个个体。

假设有4个豌豆A、B、C、D，它们的适应度值如下：

适应度值越大越好，则它们组成的轮盘如下图：

但由于轮盘赌选择是一个随机选择过程，A、B、C、D进行轮盘赌选择后产生的下一代也有可能出现A、A、A、A的情况，即虽然有些个体的适应度值不好，但是运气不错，也被选择留到了下一代。
遗产算法的三个主要操作介绍完了，下面我们来看看遗传算法的总体流程：

前面我们说了遗传算法的流程及各个操作，那么对于实际的问题我们应该如何将其编码为基因呢？

对于计算机来所所有的数据都使用二进制数据进行存放，如float类型和double类型的数据。
float类型的数据将保存为32位的二进制数据：1bit（符号位） 8bits（指数位） 23bits（尾数位）
如-1.234567f，表示为二进制位

Double类型的数据将保存为64位的二进制数据：1bit（符号位） 11bits（指数位） 53bits（尾数位）
如-1.234567d，表示为二进制为

可以看出同样的数值不同的精度在计算机中存储的内容也不相同。之前的适应度函数 ，由于有两个double类型的参数，故其进行遗传算法基因编码时，将有128位基因。
虽然基因数较多，但好在每个基因都是0或者1，交叉及变异操作非常简单。

相比二进制编码，十进制编码的基因长度更短，适应度函数 有两个输入参数，那么一个个体就有2个基因，但其交叉、变异操作相对复杂。
交叉操作
方案1：将一个基因作为一个整体，交换两个个体的等位基因。
交换前

交换第1位基因后

方案2：将两个个体的等位基因作为一个整体，使其和不变，但是值随机
交换前

交换第1位基因后

假设A、B豌豆的第一位基因的和为40，即 ,第一位基因的取值范围为0-30，那么A、B豌豆的第一位基因的取值范围为[10,30],即 为[0,30]的随机数， 。
变异操作，将随机的一位基因设置为该基因取值范围内的随机数即可。

这个过程说起来简单但其实现并不容易。

我们要将它们的值映射到一个轴上才能进行随机选择，毕竟我们无法去绘制一个轮盘来模拟这个过程

如图，将ABCD根据其值按顺序排列，取[0,10]内的随机数r，若r在[0,1]内则选择A,在(1,3]内则选择B,在(3,6]内则选择C,在(6,10]则选择D。
当然这仍然会有问题，即当D>>A、B、C时，假如它们的值分布如下

那么显然，选D的概率明显大于其他，根据轮盘赌的选择，下一代极有可能全是D的后代有没有办法均衡一下呢？
首先我想到了一个函数，

不要问我为什么我不知道什么是神经什么网络的，什么softmax、cnn统统没听说过。

这样一来，它们之间的差距没有之前那么大了，只要个体适应度值在均值以上那么它被保留至下一代的概率会相对较大，当然这样缩小了个体之间的差距，对真正优秀的个体来说不太公平，相对应，我们可以在每次选择过程中保留当前的最优个体到下一代，不用参与轮盘赌这个残酷的淘汰过程。

最令人高兴的环节到了，又可以愉快的凑字数了。

由于遗传算法的收敛速度实在是太慢，区区50代，几乎得不到好的结果，so我们把它的最大迭代次数放宽到200代。

使用二进制编码来进行求解
参数如下：

求解过程如上图，可以看出基因收敛的很快，在接近20代时就图中就只剩一个点了，之后的点大概是根据变异操作产生。看一下最后的结果。

可以看出最好的结果已经得到了最优解，但是10次实验的最差值和平均值都差的令人发指。为什么会这样呢？

问题出在二进制编码上，由于double类型的编码有11位指数位和52位小数位，这会导致交叉、变异操作选到指数位和小数位的概率不均衡，在小数位上的修改对结果的影响太小而对指数为的修改对结果的影响太大，
如-1.234567d，表示为二进制为

对指数为第5位进行变异操作后的结果为-2.8744502924382686E-10，而对小数位第5为进行变异操作后的结果为-1.218942。可以看出这两部分对数值结果的影响太不均衡，得出较好的结果时大概率是指数位与解非常相近，否则很难得出好的结果，就像上面的最差值和均值一样。
所以使用上面的二进制编码不是一个好的基因编码方式，因此在下面的实验中，将使用十进制来进行试验。

使用:十进制编码来进行求解
参数如下：

我们可以看到直到40代时，所有的个体才收束到一点，但随后仍不断的新的个体出现。我们发现再后面的新粒子总是在同一水平线或者竖直线上，因为交叉操作直接交换了两个个体的基因，那么他们会相互交换x坐标或者y坐标，导致新个体看起来像在一条直线上。
我们来看看这次的结果。

这次最优值没有得到最优解，但是最差值没有二进制那么差，虽然也不容乐观。使用交换基因的方式来进行交叉操作的搜索能力不足，加之轮盘赌的选择会有很大概率选择最优个体，个体总出现在矩形的边上。
下面我们先改变轮盘赌的选择策略，使用上面的sigmod函数方案，并且保留最优个体至下一代。

使用:十进制编码来进行求解
参数如下：

看图好像跟之前的没什么区别，让我们们看看最终的结果：

可以看出，最优值没有什么变化，但是最差值和平均值有了较大的提升，说明该轮盘赌方案使算法的鲁棒性有了较大的提升。在每次保留最优个体的情况下，对于其他的个体的选择概率相对平均，sigmod函数使得即使适应度函数值相差不太大的个体被选到的概率相近，增加了基因的多样性。

使用:十进制编码来进行求解，改变交叉方案，保持两个个体等位基因和不变的情况下随机赋值。
参数如下：

上图可以看出该方案与之前有明显的不同，在整个过程中，个体始终遍布整个搜索空间，虽然新产生的个体大多还是集中在一个十字架型的位置上，但其他位置的个体比之前的方案要多。
看看结果，

这次的结果明显好于之前的所有方案，但仍可以看出，十进制的遗传算法的精度不高，只能找到最优解的附近，也有可能是算法的收敛速度实在太慢，还没有收敛到最优解。

遗传算法的探究到此也告一段落，在研究遗传算法时总有一种力不从心的感觉，问题可能在于遗传算法只提出了一个大致的核心思想，其他的实现细节都需要自己去思考，而每个人的思维都不一样，一万个人能写出一万种遗传算法，其实不仅是遗传算法，后面的很多算法都是如此。
为什么没有对遗传算法的参数进行调优，因为遗传算法的参数过于简单，对结果的影响的可解释性较强，意义明显，实验的意义不大。

遗传算法由于是模仿了生物的进化过程，因此我感觉它的求解速度非常的慢，而且进化出来的结果不一定是最适应环境的，就像人的阑尾、视网膜结构等，虽然不是最佳的选择但是也被保留到了今天。生物的进化的随机性较大，要不是恐龙的灭绝，也不会有人类的统治，要不是人类有两只手，每只手有5根手指，也不会产生10进制。
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（五）粒子群算法（3）
下一篇 优化算法笔记（七）差分进化算法

优化算法matlab实现（六）遗传算法matlab实现

⑼ 遗传算法的模拟 数据结构题目

我这里给出了一个简单的模板如果需要编代码填代码的地方已经有提示了
/*package otherFile;

import java.util.Random;
import tGraph.TdcppGraph;
import shuffP.*;
*/
/**************
*
* @author vaqeteart
* 这里是遗传算法的核心框架遗传算法的步骤：
* 遗传算法核心部分的算法描述
* 算法步骤：
* 1、初始化
* 1.1、生成初始种群编码
* 1.2、计算每个个体的适配值。
* 1.3、记录当前最优适配值和最优个体
* 2、选择和遗传，
* 2.0、若当前最优适配值多次小于已有的最优适配值（或相差不大）很多次，或者进化的次数超过设定的限制，转4。
* 2.1、按照与每个个体的适配值成正比的概率选择个体并复制，复制之后个体的数目和原始种群数目一样。
* 2.2、（最好先打乱复制后种群的个体次序）对复制后个体进行两两配对交叉，生成相同数目的的下一代种群。
* 2.3、对下一代种群按照一定的概率进行变异
* 2.4、计算每个个体的适配值。
* 2.5、记录当前最优适配值和最优个体
* 2.6、转2
* 3、返回当前最优适配值以及其对应的编码，结束。
*
* 注意：
* 1.这里的内容相当于一个模板，编写具体的遗传算法的时候，可以按照这个模板的形式编写。
* 2.应该填写代码的地方都有提示的标记。
*/

public class GAKernel
{
//number of population
int popNum;//set the number to 20 in constructor
//current evolution times
int evolutionTim;
//limit of the evolution times
int evolutionLim;//set the number to 20 in constructor
//unaccepted times
//int eliminTim;
//limit of unaccepted times
//int eliminLim;
//current best euler code
//int curBestCode[];
//current best fitness
int curBestFitness;
//fitness of every indivial
int iFitness[];
//fator of compute the fitness
int factor;
//..................other members.............................................

//the graph
//public TdcppGraph tpGraph;
//the eula code group
//int codes[][];
//every population
//
//constructor
GAKernel(TdcppGraph tG,int eulerCode[])
{
popNum = 32;//2*2*2*2*2
//factor = Integer.MAX_VALUE / popNum;//to avoid overflow when select,for every fitness
evolutionTim = 0;/////
evolutionLim = 15;///////
//this.tpGraph=new TdcppGraph(tG);
//eliminTim = 0;
//eliminLim
curBestFitness = 0;
//curBestCode = new int[eulerCode.length];
//for(int i = 0; i < curBestCode.length; ++i)
//{
// curBestCode[i] = eulerCode[i];
//}
//??curBestFitness
iFitness = new int[popNum];
//codes = new int[popNum][];//lines
for(int i = 0; i < popNum; ++i)
{
//codes[i] = new int[eulerCode.length];
iFitness[i] = 0;
}
System.out.println("构造函数,需要填入代码");
}
//initialize the originalpopulation
void initPopulation()
{
//.......................初始化种群........................................
//int tmpCode[] = new int[curBestCode.length];
//get the initial indivial
//for(int i = 0; i < curBestCode.length; ++i)
//{
// tmpCode[i] = curBestCode[i];
// codes[0][i] = tmpCode[i];
//}
//ShuffEP s = new ShuffEP(this.tpGraph);
//for(int i = 1; i < popNum; ++i)
//{
// s.shuff(tmpCode);
// for(int j = 0; j < tmpCode.length; ++j)
// {
// codes[i][j] = tmpCode[j];
// }
//}
System.out.println("初始化种群,需要填入代码");
//get the initial fitness to the member iFitness
computeFitness();
//get the initial best indivial and fitness
recordBest();
}
//compute the fitness of every indivial in current population
void computeFitness()
{
//........................计算每个个体适应度.......................
//int time = 0;
//for(int i = 0; i < popNum; ++i)
//{
// time = 0;
// for(int j = 0; j < codes[i].length - 1; ++j)
// {
// time += tpGraph.Edge(codes[i][j], codes[i][j + 1]).getCost(time);
// }
// iFitness[i] = factor - time;
// if(iFitness[i] < 0)
// {
// System.out.println("错误，某个个体适应度过小使得适配值出现负数");//lkdebug
// System.exit(1);
// }
//}
System.out.println("计算每个个体适应度,需要填入代码");
}
//record the current best fitness and the according indivial
void recordBest()
{
int bestIndex = -1;
for(int i = 0; i < popNum; ++i)
{
if(curBestFitness < iFitness[i])
{
curBestFitness = iFitness[i];
bestIndex = i;
}
}
//............................记录最优个体.............................
if(bestIndex > -1)
{
// for(int i = 0; i < curBestCode.length; ++i)
// {
// curBestCode[i] = codes[bestIndex][i];
// }
}
System.out.println("记录最优个体,需要填入代码");
}
//selection and reproce indivial in population
void selIndivial()
{
int tmpiFitness[] = new int[iFitness.length];
tmpiFitness[0] = iFitness[0];
//建立临时群体用于选择交换
//.................................复制个体...............................
//清除原来的群体
//int tmpCode[][] = new int[popNum][];
//for(int i = 0; i < codes.length; ++i)
//{
// tmpCode[i] = new int[codes[i].length];//???
// for(int j = 0; j < codes[i].length; ++j)
// {// to tmpCode and reset codes
// tmpCode[i][j] = codes[i][j];
// codes[i][j] = -1;
// }
//}
System.out.println("复制个体,需要填入代码");
for(int i = 1; i < tmpiFitness.length; ++i)
{
tmpiFitness[i] = tmpiFitness[i - 1] + iFitness[i];
//iFitness[i] = 0;
}
//轮盘赌选择个体
for(int i = 0; i < popNum; ++i)
{
int rFit = new Random().nextInt(tmpiFitness[tmpiFitness.length - 1]);
for(int j = 0; j < tmpiFitness.length; ++j)
{
if(rFit < tmpiFitness[j])
{
rFit = j;//record the index of the indivial
break;
}
}
if(rFit == 0)
{
iFitness[i] = tmpiFitness[rFit];
}
else
{
iFitness[i] = tmpiFitness[rFit] - tmpiFitness[rFit - 1];// fitness
}
//....................................选择个体...........................
//for(int j = 0; j < tmpCode[rFit].length; ++j)
//{
// codes[i][j] =tmpCode[rFit][j];
//}
System.out.println("选择个体，需要填入代码");
}
//get the copied fitness in iFitness
}
//match every two indivial and cross the code
void matchCross()
{
//........................需要填入代码................................
System.out.println("配对交叉,需要填入代码");
}
//mutate by a specifical probability
void mutate()
{
//........................按照一定的概率进行变异.......................
System.out.println("按照一定的概率进行变异,需要填入代码");
}
//evolve current population
void evolve()
{
selIndivial();
matchCross();
mutate();
}
//compute the approximative best value by GA
//find approximative best solution by GA
public void compute()
{
initPopulation();
//while((evolutionTim < evolutionLim) && (eliminTim < eliminLim))
while(evolutionTim < evolutionLim)
{
evolve();
//get the initial fitness to the member iFitness
computeFitness();
//get the initial best indivial and fitness
recordBest();
++evolutionTim;
}
}
}