Phân tích thiết kế giải thuật

                            Thuật Toán Gene 
              ( tk có kinh nghiệm)

1 Thuật toán Gene( GAs)
+ Giới thiệu

+ Mô tả:

+ Cài Đặt:

+ Nội dung

1 Một số bài toán

2 Mã Hóa
+ Mã hóa nhị phân

=> ví dụ: bt Knapsack 01

+ Mã hóa hoán vị (permutasion encoding)

=> vị dụ: bài toán người bán hàng

+ Mã hóa giá trị

+ Mã hóa dạng cây

3 Khởi tạo quần thể
+ ví dụ bt Người bán hàng:

4 Hàm Thích Nghi
+ Knapsack 01:

=> chỉ cần thỏa mãn tiêu chí ban đầu weight< 20
+ bài toán TPS

5 Phương pháp lựa chọn

+ Roulette Wheel Sellection

+ Rank Selection

+ Steady-State Selection

=> Những cá thể nổi trội được đưa ngay sang thế hệ kế tiếp( ko cần lai ghép,..) những cá thể quá yếu => bỏ luôn ko cho sinh sản

+ Chọn Cá thể ưu tú - Elitism

6 Crossover và Mutation
6.1 Crossover cho mã hóa nhị phân

+ Two Point Crossover

6.2 Mutation cho mã nhị phân

6.3 Crossover cho mã hóa hoán vị

+ Ví dụ: bài toán TSP

6.4 Mutation cho mã hóa hoán vị

6.5 Crossover cho mã hóa giá trị

6.6 Mutation cho mã hóa giá trị

6.7 Crossover cho mã hóa Cây

6.8 Mutation cho mã hóa Cây

6.9 Xác suất Crossover và Mutation
7 Tiêu chuẩn kết thúc

8 Một số gợi ý

9 Ưu Điểm

10 Nhược điểm

Code in Dev C++ 

 file Text:
8
6  7  8  7  9  6  4  6
2  5  5  4  3  2  1  5
20

Code:
#include<iostream>
#include<fstream>
#include<list>
#include <stdlib.h>
#include<time.h>
using namespace std;

int soCaThe;
int Data[20][20];
int Capacity;


void Nhap(int &soCaThe,int Data[20][20],int &Capacity)
{
fstream f;
f.open("1.txt");
f>>soCaThe;
for(int i=0;i<2;i++)
{
for(int j=0;j<soCaThe;j++)
{
f>>Data[i][j];
}
}
f>>Capacity;
}

void Xuat(int soCaThe,int Data[20][20],int Capacity)
{
for(int i=0;i<2;i++)
{
if(i==0) cout<<"Khoi Luong: ";
else cout<<"Gia Tri:    ";
for(int j=0;j<soCaThe;j++)
{
cout<<Data[i][j]<<"   ";
}
cout<<endl;
}
cout<<"Suc chua cua tui: "<<Capacity<<endl;
}

class Chromosome
{
public:
int gene[10];
int Weight;
int Value;

void Create(int soCaThe,int Data[20][20],int t);
void Xuat(int soCaThe);

double DiemThichNghi();
Chromosome operator= (Chromosome ch2);
};

Chromosome Chromosome::operator=(Chromosome ch2)
{
this->Weight=ch2.Weight;
this->Value= ch2.Value;
for(int j=0;j<soCaThe;j++)
{
this->gene[j]=ch2.gene[j];
}
}

double Chromosome::DiemThichNghi()
{
if(Weight<=Capacity) return Value;
else{
double tiLeMax=1.0*Data[1][0]/Data[0][0];
for(int j=1;j<soCaThe;j++)
{
if(tiLeMax<1.0*Data[1][j]/Data[0][j]){
tiLeMax= 1.0*Data[1][j]/Data[0][j];
}
}
return 1.0*Value-(Weight-Capacity)*tiLeMax-0.3*Value;
}
}

void Chromosome::Create(int soCaThe,int Data[20][20],int t)
{
srand(t);
Weight=Value=0;
for(int j=0;j<soCaThe;j++)
{
if(rand()%2==0){
Weight+= Data[0][j];
Value+= Data[1][j];
gene[j]=1;
}
else{
gene[j]=0;
}
}
}

void Chromosome::Xuat(int soCaThe)
{
for(int j=0;j<soCaThe;j++)
{
cout<<gene[j];
}
cout<<"   tong Khoi Luong: "<<Weight<<"  Gia tri: "<<Value<<" Diem Thich nghi: "<<DiemThichNghi()<<endl;
}

class ListChromosome
{
public:
int soNST;
int soGene;
int soParent;
Chromosome DsChromosome[30];

Chromosome Cha,Me;
Chromosome Con1,Con2;

Chromosome ChaDotBien;
Chromosome ConDotBien;

int mutationRate;//ty le lai ghep
int crossoverRate;//ty le dot bien
int numIteration;// so lan lap lai qua trinh lai ghep dot bien

void Create(int soCaThe,int Data[20][20]);
void Xuat(int soCaThe);

void SapXep();//theo diem thich nghi
void RankSelection(int t);
void ChonKetHop(int t);//cho Laighep
void LaiGhep();
void DotBien(int t);

void ThanhQua(int t);// ket qua doi con sau numIteration vong lap
};

void ListChromosome:: ThanhQua(int t)//hat giong gieo ngau nhien
{
srand(t);
for(int i=0;i<numIteration;i++)//100 vong lap
{
Chromosome listTemp[20];
for(int i=0;i<soNST;i++)
{
listTemp[i]=DsChromosome[i];
}

while (soParent>1)
{
if(rand()%(mutationRate+crossoverRate)<mutationRate)
{
ChonKetHop(t);
LaiGhep();
}
else{
DotBien(t);
}
}

for(int i=0;i<soNST;i++)
{
DsChromosome[i]=listTemp[i];
}

SapXep();
RankSelection(t);
soGene=soParent=soNST;
SapXep();
}
}

void ListChromosome::DotBien(int t)
{
srand(t);
int k=rand()%soParent;//chon cha dot bien
ConDotBien= ChaDotBien=DsChromosome[k];
for(int i=k;i<soParent-1;i++)
{
DsChromosome[i]=DsChromosome[i+1];
}
soParent--;

int h=rand()%soCaThe;//chon gene dot bien
if(ConDotBien.gene[h]==0){
ConDotBien.gene[h]==1;
}
else{
ConDotBien.gene[h]=0;
}
}

void ListChromosome::LaiGhep()
{
int n=soCaThe/2+1;//  singer point Crossover
Con1.Weight=Con2.Weight=Con1.Value=Con2.Value=0;
for(int i=0;i<n;i++)
{
Con1.gene[i]=Cha.gene[i];
Con2.gene[i]=Me.gene[i];
}

for(int i=n;i<soCaThe;i++)
{
Con1.gene[i]=Me.gene[i];
Con2.gene[i]=Cha.gene[i];
}

for(int i=0;i<soCaThe;i++)
{
if(Con1.gene[i]==1){
Con1.Weight+=Data[0][i];
Con1.Value+= Data[1][i];
}
if(Con2.gene[i]==1){
Con2.Weight+=Data[0][i];
Con2.Value+= Data[1][i];
}
}

DsChromosome[soGene]=Con1;
soGene++;
DsChromosome[soGene]=Con2;
soGene++;
}

void ListChromosome::ChonKetHop(int t)
{
srand(t);/// can sua

int i=rand()%soParent;
Cha=DsChromosome[i];
for(int k=i;k<soParent-1;k++)
{
DsChromosome[k]=DsChromosome[k+1];
}
soParent--;

int j=rand()%soParent;
Me=DsChromosome[j];
for(int k=j;k<soParent-1;k++)
{
DsChromosome[k]=DsChromosome[k+1];
}
soParent--;
}

void ListChromosome::RankSelection(int t)
{
srand(t);//sua lai
int s=0;// tong cac thu hang
int a[30];//diem xep hang ung voi moi chromosome,,,

// ca the co ham thich nghi tot nhat dk chon sang luon doi sau
for(int i=1;i<soGene;i++)
{
a[i]=soGene-i;// vi da sap xep tu ham phia truoc
s+=i;
}

int p;//random

for(int j=1;j<soNST;j++)
{
p=rand()%s;
int n=0;
for(int i=1;i<soGene;i++)
{
n+=a[i];
if(p<n){
DsChromosome[j]=DsChromosome[i];
//loai no khoi danh sach tuyen chon
s-=a[i];
for(int k=i;k<soGene-1;k++)
{
DsChromosome[k]=DsChromosome[k+1];
}
soGene--;
break;
}
}
}
}

void ListChromosome::SapXep()
{
for(int i=0;i<soGene-1;i++)
{
for(int j=i+1;j<soGene;j++)
{
if(DsChromosome[i].DiemThichNghi()<DsChromosome[j].DiemThichNghi())
{
Chromosome temp=DsChromosome[i];
DsChromosome[i]=DsChromosome[j];
DsChromosome[j]=temp;
}
}
}
}

void ListChromosome::Create(int soCaThe,int Data[20][20])
{
srand(time(0));
int t;
cout<<endl<<"Nhap so Nhiem sac the: ";
cin>>soNST;
cout<<endl<<"Nhap so Lan lap: ";
cin>>numIteration;
cout<<endl<<"Nhap ty le Lai ghep(>0 <100):  ";
cin>>crossoverRate;
mutationRate=100-crossoverRate;
soGene=soParent=soNST;
for(int i=0;i<soNST;i++)
{
t=rand()%100;
DsChromosome[i].Create(soCaThe,Data,t);
}
}

void ListChromosome::Xuat(int soCaThe)
{
for(int i=0;i<soNST;i++)
{
DsChromosome[i].Xuat(soCaThe);
}
}

int main()
{
srand(time(0));
Nhap(soCaThe,Data,Capacity);
Xuat(soCaThe,Data,Capacity);
ListChromosome list1;
list1.Create(soCaThe,Data);
list1.SapXep();
cout<<"Trang thai ban dau la: "<<endl;
list1.Xuat(soCaThe);

cout<<"Trang thai ket thuc la: "<<endl;
int t= rand()%100;
list1.ThanhQua(t);
list1.Xuat(soCaThe);
}