遺傳演算法的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;
}
}
}