遗传算法实验报告
姓名:张虎 学号:E200902056
一、实验目的:
熟悉和掌握遗传算法的运行机制和求解的基本方法。
遗传算法是一种基于空间搜索的算法,它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论,模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下:
(1)随机产生一个确定长度的特征字符串组成的初始种群。。
(2)对该字符春种群迭代地执行下面的步骤a和步骤b,直到满足停止准则为止:
a计算种群中每个个体字符串的适应值;
b应用复制、交叉和变异等遗传算子产生下一代种群。
(3)把在后代中表现的最好的个体字符串指定为遗传算法的执行结果,即为问题的一个解。
二、实验原理和题目:
通过编码、设置种群、设置适应度函数、遗传操作、解码产生需要的解。
f(x)=x*sin(x)+1, xÎ[0,2p],求解f(x)的最大值和最小值。
三、实验条件
硬件:微型计算机。
语言:本实验选用的为C#语言。
四、实验内容:
建造针对f(x)的遗传算法程序,然后进行运行求解。
五、实验步骤:
1. 确定基本功能:本实验是实现f(x)的最大值和最小值的求解。
2. 对f(x)进行编码:用一个二进制矢量表示一个染色体,由染色体来代表变量x的实数值,这里精度取小数点后6位数,变量x的域长为2p,整个区间被分为2p*1000000个等长的区间。由于2p*1000000在23位二进制数的表示范围呢,所以,编码长度为23位。试验中用函数GetRandomBinaryArray(int count, int i);来实现。
3. 设计适应度函数:由于要求f(x)的最值,所以适应度函数就是f(x)。
4. 针对f(x)的设计并且实现遗传算法程序:遗传操作主要包括复制、交叉和变异。复制是直接将父代遗传给子代,即根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。交叉从能进入下一代的个体中选出两个,将两者的部分码值进行交换。变异是根据变异概率选出一个个体,随机对其某位编码进行改变。复制由void Selection(bool flag);实现;交叉由void Crossed();实现;变异由void Mution();实现。
5. 设计初始种群:默认设置为50个随机产生的23位字节的染色体,可以通过输入来设置种群规模。
6. 调试交叉和变异概率:在常用的交叉和变异概率范围内,结果随交叉和变异的概率的改变而改变,之间差异相对来说不太明显
7. 实验参数:实验中主要的参数有遗传代数、群体规模、交叉概率、变异概率。
实验结果:
求最大值
求最小值:
核心程序:
public EGAlgorith(double min, double max, double crossRate, double varRate,int precision, int populationNumeber)
{
m_minValue = min;
m_maxValue = max;
m_crossRate = crossRate;
m_varRate = varRate;
m_populationNumber = populationNumeber;
m_length = max - min;
m_populations = new string[m_populationNumber][];
m_doublePopulation = new double[m_populationNumber];
m_fit = new double[m_populationNumber];
m_codeLength = Convert.ToString(Convert.ToInt32(m_length * Math.Pow(10, precision)),2).Length;
//初始化种群
for(int i = 0; i < m_populationNumber; i++)
{
m_populations[i] = GetRandomBinaryArray(m_codeLength, i);
}
}
//产生随机数组
public static string[] GetRandomBinaryArray(int count, int i)
{
Random rnd = new Random(DateTime.Now.Millisecond + i);
byte[] keys = new byte[count];
rnd.NextBytes(keys);
string[] items = new string[count];
for (int j = 0; j < count; j++)
{
if(keys[j] > 127)
{
items[j] = "1";
}
else
{
items[j] = "0";
}
}
return items;
}
//根据适应度进行选择最值
public void FromFitSelect(bool flag)
{
//int[] indexs = new int[m_populationNumber];
int winIndex = 0;
double tempMin = double.MinValue;
double tempMax = double.MaxValue;
if(flag)
{
for (int i = 0; i < m_populationNumber; i++)
{
//indexs[i] = i;
if (m_fit[i] > tempMin)
{
tempMin = m_fit[i];
winIndex = i;
}
}
}
else
{
for (int i = 0; i < m_populationNumber; i++)
{
if (m_fit[i] < tempMax)
{
tempMax = m_fit[i];
winIndex = i;
}
}
}
//int winIndex = GetMaxIndex(indexs);
m_winCode = m_populations[winIndex];
m_winValue = m_doublePopulation[winIndex];
m_winFit = m_fit[winIndex];
}
//选择方法
private void Selection(bool flag)
{
int size = 3; //竞争规模
string[][] tempPopulation = new string[m_populationNumber][];
for (int i = 0; i < m_populationNumber; i++)
{
int[] inSelect = GetRandomIntArray(0, m_populationNumber - 1, size, i);
int winIndex = GetMaxIndex(inSelect,flag);
string[] tempStr = new string[m_codeLength];
for (int j = 0; j < m_codeLength; j++)
{
tempStr[j] = m_populations[winIndex][j];
}
tempPopulation[i] = tempStr;
}
m_populations = tempPopulation;
}
//交叉方法
private void Crossed()
{
int[] crossRate = GetRandomIntArray(0, 1000, m_populationNumber, 3);
for (int i = 0; i < m_populationNumber; i++)
{
if (crossRate[i] <= m_crossRate * 1000)
{
int[] doubCrossIndex = GetRandomIntArray(0, m_populationNumber - 1, 2, 2);
Random rnd = new Random();
int crossPosition = rnd.Next(m_codeLength);
string[] tempStr = new string[m_codeLength];
for (int j = 0; j < crossPosition; j++)
{
tempStr[j] = m_populations[i][j];
}
for (int k = crossPosition; k < m_codeLength; k++)
{
tempStr[k] = m_populations[doubCrossIndex[0]][k];
}
m_populations[i] = tempStr;
}
}
}
//变异方法
private void Mution()
{
int[] varRate = GetRandomIntArray(0, 1000, m_populationNumber, 3);
for (int i = 0; i < m_populationNumber; i++)
{
Random rnd = new Random(i * i);
int varPosition = rnd.Next(m_codeLength);
if(varRate[i] < m_varRate * 1000)
{
if (m_populations[i][varPosition] == "0")
{
m_populations[i][varPosition] = "1";
}
else
{
m_populations[i][varPosition] = "0";
}
}
}
}
//遗传操作
public void Evaluaton(bool flag)
{
ComputeIndividual();
ComputeFit();
FromFitSelect(flag);
Selection(flag);
Crossed();
Mution();
}
第二篇:遗传算法实验报告
一、实验题目
求解线性约束优化问题的遗传算法
将物品由7个起运站运到7个目的地;已知由i站运到j地的单位运费是,表示i站的供应量,表示j地的需求量,表示从i站到j地的运量。 (i, j =1,2,…,7)
约束条件:
目标函数为:
罚函数为:
其中,k=1,P=1/14,f为第t代群体的平均适应度,T为最大运行代数,为约束的违反度。
费用参数表如下:
使用策略:通用遗传算法模型、精英保存策略、轮盘赌法策略选择个体交叉和变异,对上述例子进行了算法的测试,种群个体大小为40,迭代10000次,得到比较稳定的结果。每次运行的结果是得到一个相对稳定的、代价小的目标值。实验结果:在当前条件下,在初始种群的40个个体,经过10000次迭代得到最低运费为1279,并且程序多次运行结果都稳定在1300左右。
二、实验环境
操作系统:Microsoft Windows XP Professional
软件:Microsoft Visual C++ 6.0
三、实验设计原理
1. 实验内容分析
本实验采用遗传算法求解带约束条件的函数优化问题。
2. 遗传算法的思想
生物的进化是以集团为主体的。与此相对应,遗传算法的运算对象是由M个个体所组成的集合,称为群体。与生物一代一代的自然进化过程相类似,遗传算法的运算过程也是一个反复迭代过程,第t代群体极为P(t),进过一代遗传和进化后,得到第t+1代群体,他们也是由多个个体组成的集合,记做P(t+1)。这个群体不断地经过遗传和进化操作,并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代,这样最终在群体中将会得到一个优良的个体X,它所对应的表现性X将达到或接近于问题的最优解。
3. 算法实现步骤
①产生初始种群:产生初始种群的方法通常有两种:一种是完全随机的方法产生的,适合于对问题的解无任何先验知识的情况;另一种是将某些先验知识转变为必须满足的一组要求,然后在满足这些要求的解中再随机地选择样本,t=0,随机产生n个个体形成一个初始群体P(t),该群体代表优化问题的一些可能解的集合;
②适应度评价函数:按编码规则,将群体P(t)中的每一个个体的基因码所对应的自变量取值代入目标函数,算出其函数值,i=1,2,…,n,越大,表示该个体有较高的适应度,更适合于f所定义的生存环境,适应度为群体进化提供了依据;
③选择:按一定概率从群体P(t)中选出m个个体,作为双亲用于繁殖后代,产生新的个体加入下一个群体P(t+1)中;
④交叉(重组):对于选中的用于繁殖的每一个个体,选择一种交叉方法,产生新的个体;
⑤变异:以一定的概率从群体P(t+1)中随机选择若干个个体,对于选中的个体,进行变异;
⑥对产生新一代的群体返回步骤③再进行评价,交叉、变异如此循环往复,使群体中个体的适应度和平均适应度不断提高,直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高,则迭代过程收敛,算法结束。
4. 算法流程图
5. 实验调试与结果分析(问题的发现、分析、解决方案与创新)
1) 程序结果如下图:
2) 收敛效果如下图:
四、实验小结及附录
通过本次实验,我了解了演化计算的基本思想,并能够运用演化计算的思想解决函数最优值问题,能够编写相应的程序。实验过程中遇到很多问题,但是进过认真分析,最终能解决问题。