演算法實驗六

A. 演算法與數據結構實驗順序表的應用實驗報告

者visual c++都行。
看看這個也許你會明白的更多一些。
實驗一 多項式相加

一、實驗目的
熟悉鏈表的使用。
掌握如何使用C語言實現鏈表的說明、創建以及結點的插入和刪除等操作。

二、實驗要求
熟悉C語言編程。

三、實驗內容
對於兩個一元多項式中所有指數相同的項，對應系數相加，若其和不為零，則構成「和多項式」的一項；對於兩個一元多項式中所有指數不相同的項，則分別復抄到「和多項式」中去。

四、實驗步驟
1. 用鏈表作一元多項式的數據結構，用C語言對鏈表作說明
2. 生成輸入一元多項式的函數
3. 輸入一元多項式A(x)和B(x)
4. 以一元多項式A(x)為和多項式，將B(x)多項式中系數加入到A(x)中去

實驗二 後綴表達式計算

一、實驗目的
熟悉棧的使用。
掌握如何使用C語言實現棧的說明、創建以及進棧和出棧等操作。

二、實驗要求
熟悉C語言編程。

三、實驗內容
先將中綴表達式（就是我們通常所見的）轉換為後綴表達式，比如 a+b*c+d 要變成 abc*+d+；轉換的方法用棧來實現，涉及到運算符的優先順序；然後用另一個棧來對後綴表達式計算結果

四、實驗步驟
1．讀入字母/數字--〉字母/數字進棧
2．讀入運算符--〉退出兩個字母/數字，用運算符計算結果，並將結果進棧
3．棧能剛好退完，則最後的即為結果。否則表明表達式有誤

實驗三 Kmp演算法

一、實驗目的
熟悉字元串的使用。
掌握如何kmp演算法實驗字元串的模式匹配。

二、實驗要求
熟悉C語言編程。

三、實驗內容
求出子串（模式串）的next，利用kmp演算法實驗模式與主串的匹配演算法。

四、實驗步驟
1．生成模式串的next函數
2．從第1個字元開始，進行模式串與主串的比較，
3．如果出現失配，將模式串的第next[j]位置開始，繼續與主串進行比較。

實驗四 Huffman 編碼

一、實驗目的
熟悉Huffman編碼方法。
了解並弄懂Huffman編碼實現信息的無損壓縮原理。

二、實驗要求
熟悉C語言編程。

三、實驗內容
1.根據給定的n個權值(w1, w2, …, wn)構成n棵二叉樹的集合F=，其中每棵二叉樹Ti中只有一個帶樹為Ti的根結點
2.在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置其根結點的權值為其左右子樹權值之和
3.在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中
4.重復2, 3，直到F只含一棵樹為止

四、實驗步驟
1．用C語言實現二叉樹的說明
2．輸入n個權值，並生成n個二叉樹
3．對n個二叉樹逐步生成Huffman樹
4．對Huffman樹的每個葉子結點生成編碼

實驗五 關鍵路徑

一、實驗目的
熟悉關鍵路徑的實現方法。
了解AOE-網以及關鍵路徑在工程實踐中的應用。

二、實驗要求
熟悉C語言編程。

三、實驗內容
根據輸入的弧，生成AOE-網。從始點開始，找出到終點的多條路徑，求這些路徑上的關鍵活動。由關鍵活動組成的從始點到終點的路徑，即為關鍵路徑。

四、實驗步驟
1．輸入e條弧，生成AOE-網的存儲結構。
2．從始點v0出發，令ve[0]=0，按拓撲有序求ve[j]
3．從終點vn-1出發，令vl[n-1]=ve[n-1]，按逆拓撲有序求vl[i]
4．根據各頂點的ve和vl值，求每條弧(活動)ai的最早開始時間e[ai]和最遲開始時間l[ai]
5．如果e[ai]=l[ai]，則ai為關鍵活動

實驗六 最短路經

一、實驗目的
熟悉最短路徑的實現方法。
了解AOE-網以及最短路徑在求解實際問題中的應用。

二、實驗要求
熟悉C語言編程。

三、實驗內容
從始點v0開始，逐步求v0到其它可達的各頂點的最短路徑，直到所有頂點計算完成為止。

四、實驗步驟
1．輸入e條弧，生成AOE-網的存儲結構。
2．初始化： S ← ;
dist[j] ← Edge[0][j], j = 1, 2, …, n-1; // n為圖中頂點個數
3.求出最短路徑的長度：
dist[k] ← min , i  V- S ;
S ← S U ;
4.修改從v0到V-S集合中各頂點的最短路徑：
dist[i] ← min,
對於每一個 i 屬於 V- S ;
5.判斷：若 S = V, 則演算法結束，否則轉 2。

實驗七 二叉排序樹

一、實驗目的
熟悉二叉排序樹的使用。
掌握如何使用C語言實現二叉樹的說明、創建以及二叉排序樹的生成等操作。

二、實驗要求
熟悉C語言編程。

三、實驗內容
給定一個記錄關鍵字的值，與二叉排序樹的根結點值比較，如果小於根結點的值，則向左子樹查找；如果大於根結點的值，則向右子樹查找。如果查找到葉子結點leaf，仍沒有找到記錄，則：如果關鍵字的值小於leaf的值，則插入該leaf結點的左邊，做leaf的左孩子，否則做leaf的右孩子。

四、實驗步驟
1．用C語言實現二叉樹的說明
2．直接將輸入的值作為根結點的值
3．與根結點比較，小於則放到左子樹上，大於則放到右子樹上。

實驗八 希爾排序

一、實驗目的
熟悉希爾排序的使用。
掌握如何使用C語言實現若干記錄的排序。

二、實驗要求
熟悉C語言編程。

三、實驗內容
先將整個待排記錄序列分割成為若乾子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，再對全體記錄進行一次直接插入排序。

四、實驗步驟
1．輸入待排序記錄
2．首先取一個整數 gap < n(待排序記錄數) 作為間隔, 將全部記錄分為 gap 個子序列, 所有距離為 gap 的記錄放在同一個子序列中
3．在每一個子序列中分別施行直接插入排序。
4．然後縮小間隔 gap, 例如取 gap = gap/2
5．重復上述的子序列劃分和排序工作，直到最後取gap = 1, 將所有記錄放在同一個序列中排序為止。

實驗九 快速排序

一、實驗目的
熟悉快速排序的使用。
掌握如何使用C語言實現若干記錄的排序。

二、實驗要求
熟悉C語言編程。

三、實驗內容
通過一趟將待排記錄分割成獨立的兩個部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小。再對兩個部分分別進行快速排序。

四、實驗步驟
1．輸入待排序的記錄，並選擇第一個記錄作為pivotkey記錄
2.從high指向的記錄開始,向前找到第一個關鍵字的值小於Pivotkey的記錄,將其放到low指向的位置,low+1
3.從low指向的記錄開始,向後找到第一個關鍵字的值大於Pivotkey的記錄,將其放到high指向的位置,high-1
4.重復2,3，直到low=high，將樞軸記錄放在low(high)指向的位置
5．重復2,3,4，直到整個記錄有序為止

實驗十 堆排序

一、實驗目的
熟悉堆排序的使用。
掌握如何使用C語言實現若干記錄的排序。

二、實驗要求
熟悉C語言編程。

三、實驗內容
首先將一個無序序列建成一個堆；然後輸出堆頂元素；在輸出堆頂元素之後，調整剩餘的元素成為一個新堆。

四、實驗步驟
1．輸入記錄，按順序創建一個完全二叉樹
2．根據篩選演算法，從最後一個結點開始，一直到根結點，逐步篩選，建造初始堆。
3．輸出堆頂記錄，將最後一個結點放到堆頂，並做篩選，重新建造一個堆
4．直到所有記錄輸出為止

B. 頁面置換演算法的實驗

#include <stdio.h>
#define PROCESS_NAME_LEN 32 /*進程名稱的最大長度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*默認內存的大小*/
#define DEFAULT_MEM_START 0 /*默認內存的起始位置*/

/* 內存分配演算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3

int mem_size=DEFAULT_MEM_SIZE; /*內存大小*/
int ma_algorithm = MA_FF; /*當前分配演算法*/
static int pid = 0; /*初始pid*/
int flag = 0; /*設置內存大小標志*/

struct free_block_type
{
int size;
int start_addr;
struct free_block_type *next;
};
struct free_block_type *free_block;

struct allocated_block
{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
struct allocated_block *allocated_block_head;

/*初始化空閑塊，默認為一塊，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{

struct free_block_type *fb;

fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL)
{
printf("No mem\n");
return NULL;
}
fb->size = mem_size;
fb->start_addr = DEFAULT_MEM_START;
fb->next = NULL;
return fb;
}

void display_menu()
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}

/*設置內存的大小*/
int set_mem_size()
{
int size;
if(flag!=0)
{ /*防止重復設置*/
printf("Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size>0)
{
mem_size = size;
free_block->size = mem_size;
}
flag=1;
return 1;
}
/*Best-fit使用最小的能夠放下將要存放數據的塊，First-first使用第一個能夠放下將要存放數據的塊，Worst-fit使用最大的能夠放下將要存放數據的塊。*/
/* 設置當前的分配演算法 */
/*分區分配演算法(Partitioning Placement Algorithm)
*/
void set_algorithm()
{
int algorithm;
printf("\t1 - First Fit\n");/*首次適應演算法(FF)：。 */
printf("\t2 - Best Fit\n");/*最佳適應演算法(BF)： */

printf("\t3 - Worst Fit\n");
scanf("%d", &algorithm);
if(algorithm>=1 && algorithm <=3) ma_algorithm=algorithm;
/*按指定演算法重新排列空閑區鏈表*/
rearrange(ma_algorithm);
}

void swap(int* data_1,int* data_2)
{
int temp;
temp=*data_1;
*data_1=*data_2;
*data_2=temp;
}

void rearrange_FF()
{
struct free_block_type *tmp, *work;
printf("Rearrange free blocks for FF \n");
tmp = free_block;
while(tmp!=NULL)
{
work = tmp->next;
while(work!=NULL)
{
if( work->start_addr < tmp->start_addr)
{ /*地址遞增*/
swap(&work->start_addr, &tmp->start_addr);
swap(&work->size, &tmp->size);
}
else
{
work=work->next;
}
}
tmp=tmp->next;
}
}
/*按BF演算法重新整理內存空閑塊鏈表(未完成)
void rearrange_BF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for BF\n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}

}

*/
/*按WF演算法重新整理內存空閑塊鏈表(未完成)
void rearrange_WF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for WF \n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}
}
*/

/*按指定的演算法整理內存空閑塊鏈表*/
int rearrange(int algorithm)
{
switch(algorithm)
{
case MA_FF: rearrange_FF(); break;
/*case MA_BF: rearrange_BF(); break; */
/*case MA_WF: rearrange_WF(); break; */
}
}

/*創建新的進程，主要是獲取內存的申請數量*/
int new_process()
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab->next = NULL;
pid++;
sprintf(ab->process_name, "PROCESS-%02d", pid);
ab->pid = pid;

printf("Memory for %s:", ab->process_name);
scanf("%d", &size);
if(size>0) ab->size=size;
ret = allocate_mem(ab); /* 從空閑區分配內存，ret==1表示分配ok*/
/*如果此時allocated_block_head尚未賦值，則賦值*/
if((ret==1) &&(allocated_block_head == NULL))
{
allocated_block_head=ab;
return 1;
}
/*分配成功，將該已分配塊的描述插入已分配鏈表*/
else if (ret==1)
{
ab->next=allocated_block_head;
allocated_block_head=ab;
return 2;
}
else if(ret==-1)
{ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 3;
}

/*分配內存模塊*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt,*pre,*r;
int request_size=ab->size;
fbt=pre=free_block;
while(fbt!=NULL)
{
if(fbt->size>=request_size)
{
if(fbt->size-request_size>=MIN_SLICE)
{
fbt->size=fbt->size-request_size;
}
/*分配後空閑空間足夠大，則分割*/

else
{
r=fbt;
pre->next=fbt->next;
free(r);
/*分割後空閑區成為小碎片，一起分配*/

return 1;
}
}
pre = fbt;
fbt = fbt->next;
}

return -1;
}

/*將ab所表示的已分配區歸還，並進行可能的合並*/
int free_mem(struct allocated_block *ab)
{
int algorithm = ma_algorithm;
struct free_block_type *fbt, *pre, *work;

fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt)
return -1;
fbt->size = ab->size;
fbt->start_addr = ab->start_addr;
/*插入到空閑區鏈表的頭部並將空閑區按地址遞增的次序排列*/
fbt->next = free_block;
free_block=fbt;
rearrange(MA_FF);
fbt=free_block;
while(fbt!=NULL)
{
work = fbt->next;
if(work!=NULL)
{
/*如果當前空閑區與後面的空閑區相連，則合並*/
if(fbt->start_addr+fbt->size == work->start_addr)
{
fbt->size += work->size;
fbt->next = work->next;
free(work);
continue;
}
}
fbt = fbt->next;
}
rearrange(algorithm); /*重新按當前的演算法排列空閑區*/
return 1;
}

/*?釋放ab數據結構節點*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;

if(free_ab == allocated_block_head)
{ /*如果要釋放第一個節點*/
allocated_block_head = allocated_block_head->next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head->next;

while(ab!=free_ab)
{
pre = ab;
ab = ab->next;
}
pre->next = ab->next;
free(ab);
return 2;
}
/*查找要刪除的進程*/
struct allocated_block* find_process(int pid)
{
struct allocated_block *temp;
temp=allocated_block_head;
while(temp!=NULL)
{
if(temp->pid==pid)
{
return temp;
}
temp=temp->next;
}
}

/*刪除進程，歸還分配的存儲空間，並刪除描述該進程內存分配的節點*/
void kill_process()
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL)
{
free_mem(ab); /*釋放ab所表示的分配區*/
dispose(ab); /*釋放ab數據結構節點*/

}
}

/* 顯示當前內存的使用情況，包括空閑區的情況和已經分配的情況 */

int display_mem_usage()
{
struct free_block_type *fbt=free_block;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL) return(-1);
printf("----------------------------------------------------------\n");

/* 顯示空閑區 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL)
{
printf("%20d %20d\n", fbt->start_addr, fbt->size);
fbt=fbt->next;
}
/* 顯示已分配區 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
while(ab!=NULL)
{
printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
ab=ab->next;
}
printf("----------------------------------------------------------\n");
return 0;
}

**********************************************************************
樓主啊，小女子給你的是殘缺版滴，要是你給我分，我就把剩下滴給你,上次在北京大學貼吧都被人騙了，世道炎涼啊O(∩_∩)O~

C. 優化演算法筆記（六）遺傳演算法

遺傳演算法(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實現