C# 遗传算法入门学习
此文仅用于记录自己的遗传算法的学习过程，对代码做了微微的改动，加了点注释，可能存在错误。
参考：https://blog.csdn.net/kyq0417/article/details/84345094
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GA
{
class Program
{
#region 全局变量
/// <summary>
/// 染色体信息
/// </summary>
private class Chromosome
{
/// <summary>
/// 用6bit对染色体进行编码，第1个元素表示正负，2-5以此存储二进制的的信息，最大表示31
/// </summary>
public int[] bits = new int[6];
/// <summary>
/// 适应值
/// </summary>
public int fitValue;
/// <summary>
/// 选择概率
/// </summary>
public double fitValuePercent;
/// <summary>
/// 累积概率
/// </summary>
public double totalProbability;
public Chromosome Clone()//染色体赋值，复制
{
Chromosome c = new Chromosome();
for (int i = 0; i < bits.Length; i++)//逐个染色体赋值
{
c.bits[i] = bits[i];
}
c.fitValue = fitValue;
c.fitValuePercent = fitValuePercent;
c.totalProbability = totalProbability;
return c;
}
}
/// <summary>
/// 变异几率
/// </summary>
public static double varProbability = 0.02;
/// <summary>
/// 染色体组;
/// </summary>
private static List<Chromosome> chromosomes = new List<Chromosome>(); //父代
private static List<Chromosome> chromosomesChild = new List<Chromosome>(); //子代
private static Random random = new Random();
/// <summary>
/// 选择类型
/// </summary>
private enum ChooseType
{
Bubble,//冒泡;
Roulette,//轮盘赌;
}
private static ChooseType chooseType = ChooseType.Roulette; //选择赌轮盘的方法
#endregion
/// <summary>
/// Main入口函数;
/// </summary>
/// <param name="args"></param>
private static void Main(string[] args)
{
Console.WriteLine("遗传算法");
Console.WriteLine("求函数最大值函数为y = x*x-31x的最大值，-31<=x<=31");
int totalTime = 30; // 迭代次数，根据结果调整
Console.WriteLine("迭代次数为: " + totalTime);
Console.WriteLine("初始化: "); //初始化;
Init(); // 输出初始化数据;
Print();
for (int i = 0; i < totalTime; i++)
{
Console.WriteLine("当前迭代次数: " + i);
//重新计算fit值;;
UpdateFitValue();
// 挑选染色体;
Console.WriteLine("挑选:");
switch (chooseType)
{
case ChooseType.Bubble:
// 排序;
Console.WriteLine("排序:");
ChooseChromosome();
break;
default:
//轮盘赌;
Console.WriteLine("轮盘赌:");
UpdateNext();
break;
}
Print(true);
//交叉得到新个体
Console.WriteLine("交叉:");
CrossOperate();
Print();
//变异
Console.WriteLine("变异:");
VariationOperate();
Print();
}
//挑选出最大适应值
int maxFit = chromosomes[0].fitValue;
for (int i = 1; i < chromosomes.Count; i++)
{
if (chromosomes[i].fitValue > maxFit)
{
maxFit = chromosomes[i].fitValue;
}
}
Console.WriteLine("最大值为: " + maxFit);
Console.ReadKey();
}
#region 打印输出
/// <summary>
/// 打印;
/// </summary>
private static void Print(bool bLoadPercent = false)
{
Console.WriteLine("=========================");
for (int i = 0; i < chromosomes.Count; i++)
{
Console.Write("第" + i + "条" + " 基因: ");
for (int j = 0; j < chromosomes[i].bits.Length; j++)
{
Console.Write(" " + chromosomes[i].bits[j]);
}
int x = DeCode(chromosomes[i].bits);
Console.Write(" x: " + x);
Console.Write(" y: " + chromosomes[i].fitValue);
if (bLoadPercent)
{
Console.Write(" 选择概率: " + chromosomes[i].fitValuePercent);
}
Console.WriteLine();
}
Console.WriteLine("=========================");
}
#endregion
#region 初始化
/// <summary>
/// 初始化
/// </summary>
private static void Init()
{
chromosomes.Clear();
int length = 30; // 染色体数量
int totalFit = 0;
for (int i = 0; i < length; i++)
{
Chromosome chromosome = new Chromosome();
for (int j = 0; j < chromosome.bits.Length; j++)
{
// 随机出0或者1;
int bitValue = random.Next(0, 2);
chromosome.bits[j] = bitValue;
}
//获得十进制的值;
int x = DeCode(chromosome.bits);
int y = GetFitValue(x);
chromosome.fitValue = y;
chromosomes.Add(chromosome);
//算出total fit;
if (chromosome.fitValue <= 0)
{
totalFit += 0;
}
else
{
totalFit += chromosome.fitValue;
}
}
}
#endregion
#region 解码，二进制装换
/// <summary>
/// 解码,二进制装换;
/// </summary>
/// <param name="bits"></param>
/// <returns></returns>
private static int DeCode(int[] bits)
{
int result = bits[1] * 16 + bits[2] * 8 + bits[3] * 4 + bits[4] * 2 + bits[5] * 1;//第一个元素判断正负，后5个元素二进制转换十进制，所能表达的最大十进制数值为31
//通过第一个元素判断正负;
if (bits[0] == 0)
{
return result;
}
else
{
return -result;
}
}
#endregion
#region 获取fitValue（适应度）
/// <summary>
/// 获取fitValue，返回值越大说明适应度越高
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
private static int GetFitValue(int x)
{
return x * x - 31 * x;//目标函数 y= x*x -31*x
}
#endregion
#region 选择
/// <summary>
/// 更新下一代;
/// 基于轮盘赌选择方法，进行基因型的选择;
/// </summary>
private static void UpdateNext()
{
// 获取总的fit;
double totalFitValue = 0;
for (int i = 0; i < chromosomes.Count; i++)
{
//适应度为负数的取0（前提知道函数的最大值一定大于0）
if (chromosomes[i].fitValue <= 0)
{
totalFitValue += 0;
}
else
{
totalFitValue += chromosomes[i].fitValue;
}
}
Console.WriteLine("累计适应度（totalFitValue） ：" + totalFitValue);
//算出每个的fit percent;
for (int i = 0; i < chromosomes.Count; i++)
{
if (chromosomes[i].fitValue <= 0) //杀掉适应度为负的基因
{
chromosomes[i].fitValuePercent = 0;
}
else
{
chromosomes[i].fitValuePercent = chromosomes[i].fitValue / totalFitValue;//计算第i个基因的适应值（第i个基于的适应值/累计适应值）
}
Console.WriteLine("第" + i + " 个体选择概率（fitValuePercent）：" + chromosomes[i].fitValuePercent);
}
////计算累积概率
//// 第一个的累计概率就是自己的概率，循环完后，便可得到累计概率的值，便于后续的赌轮盘算法
chromosomes[0].totalProbability = chromosomes[0].fitValuePercent;
double probability = chromosomes[0].totalProbability;
for (int i = 1; i < chromosomes.Count; i++)
{
if (chromosomes[i].fitValuePercent != 0) //只对出现概率概率不为0的染色体进行操作
{
chromosomes[i].totalProbability = chromosomes[i].fitValuePercent + probability;
probability = chromosomes[i].totalProbability;
}
}
chromosomesChild.Clear();
//轮盘赌选择方法,用于选出前两个;
for (int i = 0; i < chromosomes.Count; i++)
{
double chooseNum = random.NextDouble(); //生成0.0-1.0之间的随机数，用于选择
Console.WriteLine("挑选的数值：" + chooseNum);
//判断挑选的数值落在区间位置，从而确定选择的染色体
if (chooseNum < chromosomes[0].totalProbability)
{
chromosomesChild.Add(chromosomes[0].Clone());
}
else
{
for (int j = 0; j < chromosomes.Count - 1; j++) //-1是因为去除了第1个染色体
{
if (chromosomes[j].totalProbability <= chooseNum && chooseNum <= chromosomes[j + 1].totalProbability) //判断区间
{
chromosomesChild.Add(chromosomes[j + 1].Clone()); //j是从0开始的，
}
}
}
}
for (int i = 0; i < chromosomes.Count; i++)
{
chromosomes[i] = chromosomesChild[i]; //子代变父代，便于进入下一次循环
}
}
/// <summary>
/// 选择染色体;
/// </summary>
private static void ChooseChromosome()
{
// 从大到小排序;
chromosomes.Sort((a, b) => { return b.fitValue.CompareTo(a.fitValue); });
}
#endregion
#region 交叉
/// <summary>
/// 交叉操作
/// </summary>
private static void CrossOperate()
{
//选择交叉位置
int bitNum = chromosomes[0].bits.Length; //获取染色体位数
int a = random.Next(0, bitNum ); //生成0-染色体位数-1之间的随机数，
int b = random.Next(0, bitNum );
if (a > b) //交换，排序
{
int temp = a;
a = b;
b = temp;
}
Console.WriteLine("交叉范围：" + a + "— " + b);
//交叉位置处进行交叉操作（第1条和第2条进行交叉，两两一对，以此类推，染色体个数优先选择偶数个）
for (int j = 0; j < chromosomes.Count; j = j + 2)
{
for (int i = a; i <= b; i++) //从第一个随机数开始交叉 到第二个随机数结束
{
int temp = chromosomes[j].bits[i];
chromosomes[j].bits[i] = chromosomes[j + 1].bits[i];
chromosomes[j + 1].bits[i] = temp;
}
//对交叉后生成的两条新染色体（二进制转码十进制）重新计算适应值
chromosomes[j].fitValue = GetFitValue(DeCode(chromosomes[j].bits));
chromosomes[j + 1].fitValue = GetFitValue(DeCode(chromosomes[j + 1].bits));
}
}
#endregion
#region 变异
/// <summary>
/// 变异操作
/// </summary>
private static void VariationOperate()
{
int chromoNum = chromosomes.Count; //染色体数量
int geneNum = chromosomes[0].bits.Length - 1; //单个染色体基因数-1,去除用于判断正负的一个基因
int varSite = random.Next(1, chromoNum * geneNum + 1); //在所有的基因数范围中选择一个随机数
if (varSite <= chromoNum *geneNum *varProbability) //通过判断随机数是否小于等于 基因总数*变异概率 ,判断是否发生突变 //每条染色体有5个决定基因(排除第一个决定正负的基因)
{
Console.WriteLine("开始变异");
int row = random.Next(0, chromoNum ); //确定要突变的染色体编号
int col = random.Next(0, geneNum ); //确定要突变的基因
Console.WriteLine("变异的位置 :第" + row + "条染色体的第" + col + "个基因");
//0变1,1变0
if (chromosomes[row].bits[col] == 0)
{
chromosomes[row].bits[col] = 1;
}
else
{
chromosomes[row].bits[col] = 0;
}
chromosomes[row].fitValue = GetFitValue(DeCode(chromosomes[row].bits));
}
}
#endregion
#region 重新计算fit值
/// <summary>
/// 重新计算fit值;
/// </summary>
private static void UpdateFitValue()
{
for (int i = 0; i < chromosomes.Count; i++)
{
chromosomes[i].fitValue = GetFitValue(DeCode(chromosomes[i].bits));
}
}
#endregion
}
}- 上一篇 »Deap: python中的遗传算法工具箱
- 下一篇 »java遗传算法