遺伝アルゴリズムはTSPとその変式を解く
， （ ）， ：
https://blog.csdn.net/u010451580/article/details/51178225 https://blog.csdn.net/wangqiuyun/article/details/12838903
この文章を書くのは主に私がここ数日アルゴリズムを学んだので、内容は多くありません.
1.遺伝アルゴリズムの概要
遺伝的アルゴリズム(Genetic Algorithm,GA)は,生物系に対する計算機シミュレーション研究に起源がある.それは自然界の生物進化メカニズムを模倣して発展したランダムなグローバル探索と最適化方法であり、ダーウィンの進化論とメンデルの遺伝学説を参考にした.アルゴリズムは初期解を初期種群に構成し,その後遺伝,進化,変異を続け,最終的にその中から最適個体を選択することは,ビッグデータに基づいているはずである.3つの基本演算子があります:選択、交差、変異、
遺伝アルゴリズムの実施手順は以下の通りである(目標関数の最小化を例に挙げる).第一歩:t←0進化代数カウンタを初期化する;Tは最大進化代数である.初期集団P(t)としてM個の個体をランダムに生成する.第二歩:個体評価計算P(t)における各個体の適応度;(すなわち、個体の善し悪しを評価する指標)第3歩:選択演算は選択演算子を集団に作用させる.(物競天選に類似し、適者生存)第4歩:交差演算は交差演算子を集団に作用させる.(2つの個体が交差して新しい個体を繁殖する)斜体様式の第5歩:変異演算は変異演算子を集団に作用させ、以上の演算によって次世代集団P(t+1)を得る.(自己変異形成新個体)第6ステップ:終了条件判断t≦T:t←t+1ステップ2に移行する;t>T:出力解を終了する.
一般的な選択戦略:最も一般的なのは賭博輪の選択方法であり、本質は個体が選択される確率が適応度に比例することである.ここで選択する際には累積確率、すなわち個体の適応度を算出した後、個体1、個体2、個体3の適応度がそれぞれf 1、f 2、f 3、総適応度sumf=f 1+f 2+f 3となるように、個体の適応度が総適応度に占める割合を求める.個体1,2,3の累積確率はそれぞれf 1/sumf,(f 1+f 2)/sumf,(f 1+f 2+f 3)/sumfである.最後の数は必然的に1であり,0−1のホイールを構成し,ランダム数がどの範囲に落ちるか,すなわち対応個体を新種群の一員として選択する.
では、具体的にどのように選択し、どのように交差しますか?大神が整理したのを見てみましょう.https://www.cnblogs.com/legend1130/p/5333087.html一般的なクロスポリシー:https://blog.csdn.net/ztf312/article/details/82793295
実はアルゴリズムはやはり具体的な事例(コード)と結びつけて見なければならないと感じて、ちょうどアルゴリズムを見て理解しているようで分からないようで、霧の中で花を見ている感じで、やはり他の人が書いた具体的なコードを見てやっと雲を見て月を見ました.
2.具体的な応用——TSP問題
TSP問題(Travelling Salesman Problem)は旅行者問題であり、旅行セールスマン問題、貨物担問題とも訳され、数学分野で有名な問題の一つである.ある旅行商人がn都市を訪問すると仮定すると、彼は行くべき経路を選択しなければならない.経路の制限は都市ごとに1回しか訪問できず、最後に元の出発都市に戻ることだ.パスの選択目標は、必要なパスパスパスパスがすべてのパスの最小値であることです.1、基本構想:1』初期化:ランダムにscaleのパスを生成してoldpopulationに入れ、(都市は番号として、コードはパスを表す.scaleは種群の規模で、各パスは1つの個体である)2」は適応度を計算する:パスの長さが短いほど、適応度(fitness)が最も高い3)適応度が最も高いパスを選んでnewpopulationに入れ、前のbest_より優れていればtour、best_を更新tour 4』種群中の個体の累積確率を計算し,賭け輪選択法で次世代を選んでnewpopulation 5に入れる』newpopulationを交差6にする』newpopulationを変異7にする』newpopulation—>oldpopulation,8』を2-7に繰り返す
コード添付:(wangqiuyunブロガーとは異なり、私のコードに必要なデータは自分で(自分でファイルを読み書きすることもできます)、8都市の距離行列(図がないので対称行列です)
private int[][] distance = { {0, 300, 360, 210, 590, 475 , 500, 690}, {300, 0 ,380, 270, 230, 285, 200, 390}, {360, 380, 0 ,510 ,230, 765, 580, 770}, {210, 270 , 510, 0, 470, 265, 450, 640}, {590, 230, 230, 470 ,0, 515 , 260, 450}, {475, 285, 765, 265, 515, 0 ,460, 650}, {500, 200 , 580 , 450 ,260 ,460 ,0 ,190}, {690, 390 ,770, 640 ,450, 650 ,190, 0}}; )
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;
public class GA {
private int scale;//
private int cityNum; // ，
private int MAX_GEN; //
private int start = 0;
private int end = 7;
private int[][] distance =
{
{0, 300, 360, 210, 590, 475 , 500, 690},
{10000, 0 ,380, 270, 230, 285, 200, 390},
{10000, 380, 0 ,510 ,230, 765, 580, 770},
{10000, 270 , 510, 0, 470, 265, 450, 640},
{10000, 230, 230, 470 ,0, 515 , 260, 450},
{10000, 285, 765, 265, 515, 0 ,460, 650},
{10000, 200 , 580 , 450 ,260 ,460 ,0 ,190},
{10000, 10000 ,10000, 10000 ,10000, 10000 ,10000, 0}}; // */
private int bestT;//
private int bestLength; //
private int[] bestTour; //
// ， ， ， ， ，
private int[][] oldPopulation;
private int[][] newPopulation;// ，
private int[] fitness;// ，
private float[] Pi;//
private float Pc;//
private float Pm;//
private int t;//
private Random random;
public GA() {
}
/**
* constructor of GA
*
* @param s
*
* @param n
*
* @param g
*
* @param c
*
* @param m
*
*
**/
public GA(int s, int n, int g, float c, float m) {
scale = s;
cityNum = n;
MAX_GEN = g;
Pc = c;
Pm = m;
}
// ，
@SuppressWarnings("resource")
/**
* GA
* @param filename ，
* @throws IOException
*/
private void init(String filename) throws IOException {
//
/*int[] x;
int[] y;
String strbuff;
BufferedReader data = new BufferedReader(new InputStreamReader(
new FileInputStream(filename)));
distance = new int[cityNum][cityNum];
x = new int[cityNum];
y = new int[cityNum];
for (int i = 0; i < c ityNum; i++) {
// ， 1 6734 1453
strbuff = data.readLine();
//
String[] strcol = strbuff.split(" ");
x[i] = Integer.valueOf(strcol[1]);// x
y[i] = Integer.valueOf(strcol[2]);// y
}
//
// ， ， ， att48 ， 48 ， ， 10628
for (int i = 0; i < cityNum - 1; i++) {
distance[i][i] = 0; // 0
for (int j = i + 1; j < cityNum; j++) {
double rij = Math
.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
* (y[i] - y[j])) / 10.0);
// ，
int tij = (int) Math.round(rij);
if (tij < rij) {
distance[i][j] = tij + 1;
distance[j][i] = distance[i][j];
} else {
distance[i][j] = tij;
distance[j][i] = distance[i][j];
}
}
}
distance[cityNum - 1][cityNum - 1] = 0; */
bestLength = Integer.MAX_VALUE;
bestTour = new int[cityNum + 1];
bestT = 0;
t = 0;
newPopulation = new int[scale][cityNum];
oldPopulation = new int[scale][cityNum];
fitness = new int[scale];
Pi = new float[scale];
random = new Random(System.currentTimeMillis());
/*
* for(int i=0;i fitness[k]) {
maxevaluation = fitness[k];
maxid = k;
}
}
if (bestLength > maxevaluation) {
bestLength = maxevaluation;
bestT = t;// ;
for (i = 0; i < cityNum; i++) {
bestTour[i] = oldPopulation[maxid][i];
}
}
// System.out.println(" " + t + " " + maxevaluation);
// ，k ，kk
copyGh(0, maxid);// k ， 0
}
// ，k ，kk
public void copyGh(int k, int kk) {
int i;
for (i = 0; i < cityNum; i++) {
newPopulation[k][i] = oldPopulation[kk][i];
}
}
//
public void select() {
int k, i, selectId;
float ran1;
// Random random = new Random(System.currentTimeMillis());
for (k = 1; k < scale; k++) {
ran1 = (float) (random.nextInt(65535) % 1000 / 1000.0);
// System.out.println(" "+ran1);
//
for (i = 0; i < scale; i++) {
if (ran1 <= Pi[i]) {
break;
}
}
selectId = i;
// System.out.println(" " + selectId);
copyGh(k, selectId);
}
}
// ，
public void evolution() {
int k;
//
selectBestGh();
// scale-1
select();
// Random random = new Random(System.currentTimeMillis());
float r;
//
for (k = 0; k < scale; k = k + 2) {
r = random.nextFloat();// /
// System.out.println(" ..." + r);
if (r < Pc) {
// System.out.println(k + " " + k + 1 + " ...");
//OXCross(k, k + 1);//
OXCross1(k, k + 1);
} else {
r = random.nextFloat();// /
// System.out.println(" 1..." + r);
//
if (r < Pm) {
// System.out.println(k + " ...");
OnCVariation(k);
}
r = random.nextFloat();// /
// System.out.println(" 2..." + r);
//
if (r < Pm) {
// System.out.println(k + 1 + " ...");
OnCVariation(k + 1);
}
}
}
}
// ，
public void evolution1() {
int k;
//
selectBestGh();
// scale-1
select();
// Random random = new Random(System.currentTimeMillis());
float r;
for (k = 1; k + 1 < scale / 2; k = k + 2) {
r = random.nextFloat();// /
if (r < Pc) {
//OXCross1(k, k + 1);//
OXCross(k,k+1);//
} else {
r = random.nextFloat();// /
//
if (r < Pm) {
OnCVariation(k);
}
r = random.nextFloat();// /
//
if (r < Pm) {
OnCVariation(k + 1);
}
}
}
if (k == scale / 2 - 1)// L-1
{
r = random.nextFloat();// /
if (r < Pm) {
OnCVariation(k);
}
}
}
// OX
void OXCross(int k1, int k2) {
int i, j, k, flag;
int ran1, ran2, temp;
int[] Gh1 = new int[cityNum];
int[] Gh2 = new int[cityNum];
// Random random = new Random(System.currentTimeMillis());
ran1 = random.nextInt(65535) % cityNum;
ran2 = random.nextInt(65535) % cityNum;
// System.out.println();
// System.out.println("-----------------------");
// System.out.println("----"+ran1+"----"+ran2);
while (ran1 == ran2) {
ran2 = random.nextInt(65535) % cityNum;
}
if (ran1 > ran2)// ran1 ran2)// ran1 2、TSP変式出発点と終点が固定されている場合、都市0位起点、都市7を終点とすると、この路線図を有向図として想像することができ、すべての都市が都市0に到達することができず、都市7がすべての都市に到達しないことができず(無限大に設定されている)、反復を経て答え距離行列private int[][distance={0,300,360,210,590,475,500,690}を求めることができる. {10000, 0 ,380, 270, 230, 285, 200, 390}, {10000, 380, 0 ,510 ,230, 765, 580, 770}, {10000, 270 , 510, 0, 470, 265, 450, 640}, {10000, 230, 230, 470 ,0, 515 , 260, 450}, {10000, 285, 765, 265, 515, 0 ,460, 650}, {10000, 200 , 580 , 450 ,260 ,460 ,0 ,190}, {10000, 10000 ,10000, 10000 ,10000, 10000 ,10000, 0}};//距離行列*/残りのコードは上
3.制約のある遺伝アルゴリズム
TSP問題には他の制約条件はないが,多重関数を解くには0 xなどが要求される場合があり,制約条件を考慮する必要がある.私はいくつかの論文を見たことがありますが、この問題について修復できない解法があり、遺伝演算子法、罰関数法を変えて、私は深く研究したことがありません.しかし、私は1つの問題をしたことがあります.多制約条件で、罰関数を使って制約違反の程度を体現し、適応度に対して相応の罰を行い、結果も得ました.ペナルティ関数は、不可解なペナルティによって制約問題を無制約問題に変換し、制約に対する違法はターゲット関数にペナルティ項目を追加します.これは未完続き・・・
しばらく把握して、後で更新します.文章に間違いがあれば、訂正してください.ありがとうございます.
2019年7月16日火曜日