国际象棋皇后可以越过其他棋子吗（如何让8个皇后在国际象棋棋盘上和谐相处）
那天在看AIMA(Artificial Intelligence : A Modern Approach人工智能:一种当代的要领Stuart Russell著)看到了一个风趣的题目叫八皇后题目。
八皇后题目的方针是在国际象棋棋盘中安排8个皇后，使得任何一个皇后都不会进攻到其他任一皇后。(皇后可以进攻和它在统一行，统一列可能统一对角线的任何棋子)，我把这个题目抛给了周围伴侣，纷纷拿起纸笔或打开电脑上的EXCEL表格试了起来，看似简朴但都没办理，个中一位还把这个当成了上茅厕时的消遣器材。
在64个格子的国际象棋棋盘上安排8个棋子有
种安排要领，纯真用手试(还真没找到啥能力)或计较机穷举都不是好步伐，书中先容了几种算法，但我认为最风趣的是下面要说的遗传算法。
达尔文的进化论...
资料说，遗传算法(Genetic Algorithm，GA)最早是由美国的 John holland于20世纪70年月提出,该算法是按照大天然中生物体进化纪律而计划提出的。是模仿达尔文生物进化论的天然选择和遗传学机理的生物进化进程的计较模子，是一种通过模仿天然进化进程搜刮最优解的要领。该算法通过数学的方法,操作计较机仿真运算,将题目的求解进程转换成相同生物进化中的染色体基因的交错、变异等进程。在求解较为伟大的组合优化题目时,相对一些通例的优化算法,凡是可以或许较快地得到较好的优化功效。
Charles Darwin
还记得高中生物课讲的达尔文生物进化论的天然选择，孟德尔豌豆尝试和遗传学DNA双螺旋布局吗？进化论(1859)中说变革会呈此刻繁殖进程中，而且在儿女繁衍进程中以必然比例生涯下来；Gregor Mendel修羽士(1866)在豌豆身上做了尝试，把握了遗传的统计纪律；Watson和Crick(1953)确定了DNA分子的布局和它的序列。在有性生殖中儿女是由多个而不是一个生物体发生的。而现实的进化机制比大都遗传算法要富厚得多。譬喻，变异包罗DNA的反转，复制和大段移动；一些病毒借用一个生物体的DNA再插入到其他生物体的DNA里。
Watson和Crick
遗传算法和进化论
我们再来看看遗传算法，起首是一种也许的8皇后的状态
上面这幅图可以用一段序列暗示：1 5 8 6 3 7 2 4，代表8个皇后的位置，第1行第1个位置，第2行第5个位置，第3行第8个位置……第8行第4个位置
图片摘自AIMA 作者Stuart Russell
遗传算法从k个随机天生的状态开始，我们称之为种群Population。每个状态或个别，用一个有限长度的字符串暗示.图a表现了4个暗示八皇后状态的8位数字串构成的种群
遗传算法通过把两个双亲团结来天生后继，图b到e表现了发生下一代状态的进程。
在b中，每个状态都由它的方针函数或顺应度函数给出评估值。对付好的状态，顺应度函数会返回较高的值，以是在八皇后题目中，我们用不彼此进攻的皇后对的数量来暗示，最优解的顺应度是28(搜查每一个皇后与棋盘上另一个皇后是否斗嘴必要7 6 5 4 3 2 1=28)。在遗传算法中，被选择举办繁殖的概坦率接与个另外顺应度成正比，百分比在顺应度旁边。
在c中，凭证b中的概率随机选择两对举办繁殖，个别也许会被选择多次也也许一次都没有被选中。对付要配对的每对个别，在字符串中随机选择一个位置作为杂交点。
图d的交错交流，父代八皇后序列的一部门交错交流就像怙恃染色体的交错交流mom(绿色) dad(橙色)=you(绿加橙)
在d中，父串在杂交点长举办杂交而缔造出儿女。譬喻，第一对的第一个儿女从第一个父串哪里获得了前三位数字，从第二个父串哪里获得了后五位数字。
对应图e的基因突变
最后，每个位置城市凭证某个小的独立概率随机变异。在第1，第3和第4个儿女中都有一个数字产生了变异。
这样就是由初始第一代到第二代的进程，第二代个别通过顺应度函数，选择配对后有性生殖，交错交流，基因突变，又天生了第三代，不绝一再这个进程直到有一代中呈现了顺应度为28(恣意两对8皇后都不斗嘴)就找到了八皇后题目的解
想得形象些，把每一个初始随机天生的八皇后当成种群内的个别(像是天然界中的动物)，这些个别在情形是否有上风的尺度就是谁更靠近方针状态的八皇后，用顺应度函数来打分，上风越大就越能争取到交配权，从而把本身的精良性状转达下去，而顺应度低的个别则有很或许率被裁减，在有性生殖进程中，双亲互换本身序列的片断，把各自好的状态担任给下一代，假如纯真这样的话，会发明最后种群内个另外序列险些会酿成一样的(后头措施模仿简直会这样)，以是还必要基因突变，就像天然界中基因突变会发生有害的性状但也会发生越发能顺应情形的性状，而这些好的基因突变由于在顺应度函数评分时可以获得更高的分数，因此又有更或许率将本身的序列遗传给下一代，这样子代徐徐比父代更能得当情形(对应儿女八皇后比前代相互间斗嘴更小），直到某一子代呈现了完全满意前提的八皇后(天选之子)。
用Python代码模仿一下：
Fitness function 顺应度函数
(责任编辑：admin)
国学经典故事（国学经典故
西施是哪里人，她的原名叫
李斯被腰斩死得冤
历史上的嘉庆杀和