遗传算法原理、编程和应用(上课笔记)

一.遗传算法的起源和特点:

　　Genetic Algorithms是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型，是由美国Michigan大学的J.Holland教授于1975年首先提出的，是搜索最优解的一种随机化的方法。

　　遗传算法模拟生物在自然环境中的遗传和进化，是一种自适应全局优化概率搜索算法。

　　主要特点: 平行性、广泛搜索和局部精化结合、不需要过程的知识、解题范围广，容易编程、没有初值问题、 容易理解。

二、基本思想:

1、遗传算法的具体思路：进化程序（Evolution Programs)
　　特点： 借用遗传学的词汇 、薄弱的理论基础 。

2、进化过程的模拟
生物进化 遗传算法
群体 　Population
基因 　 bits
染色体 Chromosome
选择或复制 Selection
交配 Crossover
突变 Mutation
适应 Fitness

3、解的表达
　　Individual=解（数字或文字）
　　 chromosome ，a set of bits
　　Chromosomes could be:
Bit strings (0101 ... 1100)
Real numbers (43.2 -33.1 ... 0.0 89.2)
Permutations of element (E11 E3 E7 ... E1 E15)
Lists of rules (R1 R2 R3 ... R22 R23)
Program elements (genetic programming)
... any data structure ...

4、过程
{
　initialize population;evaluate population;
　while TerminationCriteriaNotSatisfied
　{
　　select parents for reproduction;
　　perform recombination and mutation;
　　evaluate population;
　}
}

Exploitation、exploration
优化，自然过程高度理想化的模拟遗传算子.

三、两种编码的方法

1、两种方法
　◎经典遗传算法 二进制，改造问题
　 ◎自然表达算法 十进制，改造遗传操作

2、二进制编码
　　bits-> string
　　00110010111111
　　遗传操作：crossover, mutation
P1 (0 1 1 0 1 0 0 0) (0 1 0 0 1 0 0 0) C1
P2 (1 1 0 1 1 0 1 0) (1 1 1 1 1 0 1 0) C2

Crossover is a critical feature of genetic algorithms:
　　It greatly accelerates search early in evolution of a populationIt leads to effective combination of schemata (subsolutions on different chromosomes)
Before: (1 0 1 1 0 1 1 0)
After: (0 1 1 0 0 1 1 0)

3、十进制编码
　　用实数 a) 位操作 b) 实数操作

四、遗传算法程序
。。。

vb.net汉诺塔递归源码

vb.net汉诺塔递归源码
-------------------------------------

Private Function Hanoi(ByVal n As Integer, ByVal x As Char, ByVal y As Char, ByVal z As Char) 　　　　　
　If n = 1 Then
　　'编号为1的盘子从x到z
　　 MoveDisc(x, 1, z)
　Else
　　'n-1个盘子从x经z到y，
　　Hanoi(n - 1, x, z, y)
　　'编号为n的盘子从x到z
　　MoveDisc(x, n, z)
　　 'n-1个盘子从y经x到z，
　　Hanoi(n - 1, y, x, z)
　End If
End Function

Private Function MoveDisc(ByVal x As Char, ByVal n As Integer, ByVal z As Char)
　 i = i + 1
　Me.RichTextBox1.AppendText(i & ":Move disc " & n & " from " & x & " to " & z & vbCrLf)
End Function

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
　Dim Num As Integer
　Dim x As Char = "x"
　Dim y As Char = "y"
　Dim z As Char = "z"
　Me.RichTextBox1.Clear()
　 i = 0
　Try
　　Num = CType(TextBox1.Text, Integer)
　　 Hanoi(Num, x, y, z)
　Catch ex As Exception
　　MsgBox("Error,please input a right number!", MsgBoxStyle.Information, "warn")
　 End Try
End Sub