目 录
摘要……………………………………………………………………………………….………………….1
前言…………………………………………………………………………………..….….......……………2
1 绪论………………………………………………………………………………….…………………….3
1.1 引言……………………………………..……….…………….……………………….…..………....3
1.2 遗传算法简介………………………..…………….………….……………..……….………………3
1.3 遗传算法的应用…………………..………………….………………………………...………….…3
1.4 适应度简介………………………..……………………….……….…………………...…………....4
1.5 C语言简介………………………………..……………………..……………………...………...…..4
2 遗传算法C语言实现……………….....….…………………………....…….…..….…………….…......5
2.1 选择算子C语言实现……………….……………………………………....……….….…...………5
2.1.1 最佳个体保存方法……………….………………………..………………..…...………………..5
2.1.2 期望值方法…………………….…………………………………………………..…..………….7
2.1.3 适应度比例方法………………………….……………………..….……………………………..8
2.2 交叉算子C语言实现……………………….………………………...…………………….…….…9
2.2.1 1点交叉…………………………....……………..…………………..…...………….....….…….9
2.2.2 1致交叉…………………………………………….……………………..………….…….……11
2.3 变异算子C语言实现……………………………………….………………..…….………….……13
2.3.1 基本变异……………………………………………….…….………………………..……..…..13
2.3.2 逆转变异…………………………………………….……………………………..……….…….14
3 应用遗传算法求解背包问题……………………………….…………….…………….….……….....…16
3.1 问题描述……………………………………….. ………….……………..………….……….……..16
3.2 基于基本遗传算法求解背包问题……………………….……………………..…....……….……..16
4 结论…………………………………………………………….……………………….. ..……...………18
参考文献……………………………………………………….……………................................................19
致谢…………………………………………………………….………..………………..….………..…….20
附录………………………………………………………….…………….........................……….………..21
基本遗传算法的C语言实现
摘要
遗传算法是1类借鉴生物界选择和自然遗传机制的随机化搜索算法。在NP-类组合优化问题的搜索优化应用中显示了超出想象的、良好的搜索性能。本文利用C语言编译遗传算法中的最佳个体保存、期望值、适应度比例选择算子，1点交叉、1致交叉算子，基本变异、逆转变异算子，最后应用遗传算法求解背包问题并将求解过程用C语言实现，并比较了不同的`选择算子优越性。
关键字：遗传算法；操作算子；C语言；背包问题
Implementation of basic Genetic algorithms with C language
Abstract
Genetic algorithm is a type of the random search algorithm which relies on the biological options natural genetic mechanisms demonstrates beyond imagination and good search capabilities in the search optimization applications of the NP-category portfolio optimization problems. Through using the C language to translate the genetic algorithms，the best-preserved，expectations，the degree of choice of a son，the cross-porint，as a cross-line，basic variations，a reverse variationis the cast application of genetic algorithms combined backpack problems with the process and fellow C language achievement，and compare the different superiority of options son .
Key word: Genetic algorithm；Operating a son；C language；Backpack problems
前 言
近代科学技术发展的显著特点之1是生命科学与工程科学的相互交叉、相互渗透和相互促进。遗传算法的蓬勃发展正体现了学科发展的这1特征和趋势。
遗传算法的内涵哲理乃是启迪于自然界生物从低级、简单、到高级、复杂，乃至人类这样1个漫长而绝妙的进化过程，借鉴于达尔文的物竞天演、优胜劣汰、适者生存的自然选择和自然遗传的机理，其本质是1种求解问题的高效并全局搜索方法。它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。
遗传算法和其它的搜索方法相比，其优越性主要表现在以下几个方便：首先，遗传算法在搜索过程中不易陷入局部最优，即使在所定义的适应度函数非连续、不规则和伴有噪声的情况下也能1极大的概率找到全局最优解；其次，由于遗传算法固有的并行性，使得它非常适合于大规模并行分布处理；此外，遗传算法易于和别的技术相结合，形成性能更优的问题求解方法。
本文考虑C语言的原始性及其适用性广的优点，用C语言实现了基本遗传算法，并对遗传算法中的最佳个体保存、期望值、适应度比例选择算子，1点交叉、1致交叉算子，基本变异、逆转变异算子进行了C语言实现，最后应用所实现的程序对1个实用问题，背包问题进行了求解，并对不同选择算子情况下的计算结果进行了比较。
