上篇初識遺傳算法講述了遺傳算法的基本思想,這篇部落格就用遺傳算法求解方程。
具體的如下:
求解方程 -x^3+7*x+13=0 在[3,4]區間的解,解精确到0.001,交叉機率0.7
變異機率0.01,疊代次數為100,字元編碼長度為10(二進制編碼)
首先簡單的分析一下:
1、編碼與解碼
題目要求的是采用二進制的編碼方式來實作,既然已經編碼了,自然就需要解碼,給定的10
位二進制編碼表示的區間範圍就是0~1023,題目的區間是[3,4]很自然的就能想到10位二進
制編碼中的0表示是就是[3,4]中的3,1023表示的就是[3,4]中的4,是以,每個二進制對應的
十進制就是((10位二進制對應的十進制數/1023)+3),這個就是解碼後的在區間[3,4]中的具體值。
2、适應度函數
這裡取的适應度函數是方程絕對值的倒數,即f=1/(|-x^3+7*x+13|)
3、選擇算子
确定選擇比例,采用輪盤賭算法。
/// <summary>
/// 模拟輪盤賭選擇算法
/// 思路:1.求适應度的總和;2.計算每個個體适應度所占的比例(除第一個之外,其他的都是疊加);
/// 3.在0~1産生随機數,這個随機數所在的區間,就是要選擇的個體
/// </summary>
/// <returns>選擇出來的優秀個體</returns>
static List<int> RWS(List<double> list)
{
List<int> select = new List<int>();
List<double> p = new List<double>();
double sum = list.Sum()/*适應度之和*/, temp = 0/*臨時變量*/;
foreach (var item in list)
{
temp += (item / sum);//疊加
p.Add(temp);//機率
}
int i, j;
for (i = 0; i < p.Count; i++)
{
temp = rd.NextDouble();//0~1的随機數
for (j = 0; j < p.Count; j++)
{
if (j == 0 && temp < p[0])
{
select.Add(0);
}
else if (temp < p[j] && temp >= p[j - 1])
{
select.Add(j);
}
}
}
return select;
}
View Code
4、交配算子
随機産生交配位,交換兩個染色體的部分基因。
/// <summary>
/// 交叉過程個體的變化(字元的替換)
/// </summary>
/// <param name="dic">參加交叉的兩個個體</param>
/// <param name="geti1">個體1</param>
/// <param name="geti2">個體2</param>
/// <returns></returns>
static List<string> Crossover_Replace(Dictionary<int, int> dic, string geti1, string geti2)
{
int index; double p;
List<string> tmp_group = new List<string>();//存放交叉過後的個體
foreach (var item in dic)
{
p = rd.NextDouble();
if (p <= crossover_probability)//機率小于0.7進行交叉
{
index = rd.Next(0, 8);
geti1 = group[item.Key];//要交叉的兩個個體
geti2 = group[item.Value];
//交叉的實作
tmp_group.Add(geti1.Insert(geti1.Length, geti2.Substring(index)).Remove(index, str_length - index));
tmp_group.Add(geti2.Insert(geti2.Length, geti1.Substring(index)).Remove(index, str_length - index));
}
else
{
tmp_group.Add(group[item.Key]);
tmp_group.Add(group[item.Value]);
}
}
return tmp_group;
}
5、變異算子
變換染色體基因的值,即0-1,1-0的變換。
/// <summary>
/// 變異過程個體的變化(0->1,1->0)
/// 思路:1.将個體的編碼轉化成字元;2.為每個字元産生一個0~1的随機數,判斷是否要進行變異操作
/// 3.要變異則将0->1,1->0
/// </summary>
/// <param name="str">個體(二進制編碼)</param>
/// <param name="result">變異後的結果</param>
/// <param name="probability">變異機率</param>
/// <returns></returns>
static string Mutation_Replace(string str, string result, double probability)
{
char[] chrArray = str.ToCharArray();
for (int i = 0; i < chrArray.Count(); i++)
{
//小于機率,替換字元
if (rd.NextDouble() <= probability)
{
if (chrArray[i] == '0')
{
chrArray[i] = '1';
}
else if (chrArray[i] == '1')
{
chrArray[i] = '0';
}
}
}
//将字元拼接成字元串
foreach (char ch in chrArray)
{
result += ch;
}
return result;
}
其中的方法,實作不唯一,時間比較敢,也沒有作一定的優化,隻是為了熟悉算法而寫的。