设为首页收藏本站
开启辅助访问 切换到宽版

 找回密码
 立即注册

QQ登录

只需一步，快速开始

热门： 51单片机 | 24小时必答区 | 单片机教程 | 单片机DIY制作 | STM32 | Cortex M3 | 模数电子 | 电子DIY制作 | 音响/功放 | 拆机乐园 | Arduino | 嵌入式OS | 程序设计

搜索
»论坛 › 电子技术分类讨论区 › 程序设计/上位机 › 启发式搜索,简单遗传算法,候选消除算法源码 人工智能实 ...
返回列表 发新帖
查看: 4087|回复: 0
收起左侧

启发式搜索,简单遗传算法,候选消除算法源码 人工智能实验报告

[复制链接]
ID:365689 发表于 2018-7-5 16:13 | 显示全部楼层 |阅读模式
本科实验报告
课程名称：   人工智能        
实验项目：1.启发式搜索2.基于产生式系统的问
题求解3简单遗传算法4候选消除算法
实验地点：实验楼110
专业班级：物联网1501 学号：2015001962
学生姓名：程*
指导教师：强*   

实验一 启发式搜索
一 实验目的
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A算法求解相关问题，理解求解流程和搜索顺序。
先熟悉启发式搜索算法；
     用C、C++、JAVA或python             语言编程实现实验内容。
二 实验内容以及原理
估价函数
在对问题的状态空间进行搜索时，为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。这些控制信息反映在估价函数中。
估价函数的任务就是估计待搜索节点的重要程度，给这些节点排定次序。估价函数可以是任意一种函数，如有的定义它是节点x处于最佳路径的概率上，或是x节点和目标节点之间的距离等等。在此，我们把估价函数f(n)定义为从初始节点经过n节点到达目标节点的最小代价路径的代价估计值，它的一般形式是：
     f(n) = g(n) + h(n)
其中g(n)是从初始节点到节点n的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从n到目标节点的最佳路径的代价估计，h(n)主要体现了搜索的启发信息。
启发式搜索过程的特性
（1）可采纳性
当一个搜索算法在最短路径存在的时候能保证能找到它，我们就称该算法是可采纳的。所有A*算法都是可采纳的。
（2）单调性
一个启发函数h是单调的，如果

    对所有的状态ni和nj，其中nj是ni的子孙，h(ni)- h(nj)≤cost(ni,nj),其中cost(ni,nj)是从ni到nj实际代价。
    目标状态的启发函数值为0，即h(Goal)=0.

具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩展的状态的f值是单调递增（不减）。
（3）信息性
比较两个启发策略h1和h2，如果对搜索空间中的任何一个状态n都有h1(n)≤h2(n)，就说h2比h1具有更多的信息性。
一般而言，若搜索策略h2比h1有更多的信息性，则h2比h1考察的状态要少。但必须注意的是更多信息性需要更多的计算时间，从而有可能抵消减少搜索空间所带来的益处。

3.常用的启发式搜索算法
（1）局部择优搜索算法（瞎子爬山法）
瞎子爬山法是最简单的启发式算法之一。该算法在搜索过程中扩展当前节点并估价它的子节点。最优的子节点别选择并进一步扩展；该子节点的兄弟节点和父节点都不再被保留。当搜索到达一种状态，该状态比它的所有子状态都要好，则搜索停止。因此，该算法的估价函数可表示为f(n) = h(n)。
在一个限定的环境下，瞎子爬山法可能会极大的提高搜索的效率，但是对整个搜索空间而言，可能得不到全局最优解。
（2）最好优先搜索法（有序搜索法）
该算法的估价函数采用f(n) = g(n) + h(n)，在搜索过程中算法使用OPEN表和CLOSE表来记录节点信息：OPEN表中保留所有已生成而未考察的节点；CLOSE表中保留所有已访问过的节点。算法在每一次搜索过程中都会对OPEN表中的节点按照每个节点的f值进行排序，选择f值最小节点进行扩展。算法的描述如下：
①把起始节点S放到OPEN表中，计算f(S),并把其值与节点S联系起来。
②若OPEN是个空表，则算法失败退出，无解。
③从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。
④把节点i从OPEN表中移出，并把它放入到CLOSED的扩展节点表中。
⑤若节点i是个目标节点，则成功退出，求得一个解。
⑥扩展i，生成其全部后继节点。对i的每个后继节点j：

    计算f(j)。
    如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f将其添加到OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。
    如果j已则OPEN表中或CLOSED表中，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f的值。若新的f值较小，则
        以此值取代旧值。
        从j指向i，而不是指向它的父辈节点。
        若节点j在CLOSED表中，则把它移回OPEN表。

⑦转向②。
三 实验仪器
macOS操作系统
四 实验步骤/设计实现
设计估价函数
设计算法步骤
编写实验程序
2
8
3
1
6
4
7

5
  • 用启发式搜索方法求解九宫问题。
1
2
3
8

4
7
6
5

五 实验代码
六 实验结果以及分析
实验二 基于产生式系统的问题求解
一 实验目的
熟悉和掌握产生式系统的构成和运行机制，掌握基于规则推理的基本方法和技术。
1.先熟悉产生式系统的基本概念；
    2.用C、C++或JAVA             语言编程实现实验内容。

二 实验内容以及原理
产生式系统（Production system）首先由波斯特（Post）于1943年提出的产生式规则（Production rule）而得名，他们用这种规则对符号串进行置换运算，后来，美国的纽厄尔和西蒙利用这个原理建立了一个人类的认知模型（1965年），同年，斯坦福大学利用产生式系统结构设计出第一个专家系统DENDRAL。
产生式系统用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对象的概念。
在产生式系统中，论域的知识分为两部份：
  • 事实：用于表示静态知识，如事物、事件和它们之间的关系；
（2）规则：用于表示推理过程和行为


一个产生式系统由三个部分组成，如图所示：
  • 总数据库：用来存放与求解问题有关的数据以及推理过程环境的当前状态的描述。
产生式规则库：主要存放问题求解中的规则。（3）控制策略：其作用是说明下一步应该选用什么规则，也就是说如何应用规则。




通常从选择规则到执行操作分三步：
  • 匹配：把当前数据库和规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。
（2）冲突解决：当有一个以上的规则条件部分和当前数据库相匹配时，就需要解决首先使用哪一条规则——冲突解决。
1）专一性排序：如果某一规则的条件部分比另一条规则的条件部分所规定的情况更为专门，则这条规则有较高的优先权。
2）规则排序：如果规则编排顺序就表示了启用的优先级，则称之为排序。
3）数据排序：把规则条件部分的所有条件按优先级次序编排起来，运行时首先使用在条件部分包含较高优先级数据的规则。4）规模排序：按规则的条件部分的规模排列优先级，优先使用被满足的条件较多的规则。
5）就近排序：把最近使用的规则放在最优先的位置。
6）上下文限制：把产生式规则按他们所描述的上下文分组，也就是说按上下文对规则分组，在某种上下文条件下，只能从与其相对应的那组规则中选择可应用的规则。
7）使用次数排序：把使用频率较高的排在前面。


（3）操作：执行规则的操作部分，经过修改以后，当前数据库将被修改。
问题描述：用基于产生式系统的方法求解传教士和野人问题
有N个传教士和N个野人来到河边准备渡河，河岸有一条船，每次至多可供K个乘渡，问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，河岸两边以及船上的野人数目总是不超过传教土的数目，即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M（传教士数）≥C（野人数）和M+C≤K的摆渡方案。

三 实验仪器
macos
四 实验步骤/设计实现
设计估价函数
设计算法步骤
编写实验程序
五 实验代码

六 实验结果以及分析
实验三 遗传算法
一 实验目的
熟悉和掌握遗传算法的基本思想和基本方法，通过实验培养学生利用遗传算法进行问题求解的基本技能，并且了解进化计算其他分支的基本思想和基本方法。


先熟悉进化计算中遗传算法的基本思想和流程；
   用C、C++、JAVA或Prolog             语言编程实现实验内容。

二 实验内容以及原理
生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则。群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化计算(evolutionary computation, EC)就是通过模拟自然物群进化的一类非常鲁棒的优化算法，它们模拟群体(其中组成群体的每个个体表示搜索问题解空间中的一个解)的集体学习过程，从任意初始群体出发，通过随机选择、变异和交叉过程，使群体进化学习到搜索空间中越来越好的区域。进化计算中选择过程使群体中适应性好的个体比适应性差的个体有更多的机会遗传到下一代中，交叉算子将父代信息结合在一起并他们遗传给下一代个体，而变异过程在群体中引入新的变种。进化计算包括遗传算法(evolutionary algorithm,EA)、进化策略(evolution strategy, ES)、进化编程(evolutionary programming, EP)、遗传编程(genetic programming, GP)。
遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一种数学仿真，是进化计算的一种最重要形式。遗传算法为那些那些难以找到传统数学模型的难题找出了一个解决方法。自从Holland于1975年在其著作《Adaptation in Natural and Artificial Systems》中首次提出遗传算法
以来，经过近30年的研究，现在已发展到一个比较成熟的阶段，并且在实际中已经得到了很好的应用。
1.简单遗传算法的构成要素
（1）染色体编码和解码方法
在实现对一个问题用遗传算法之前，我们必须先对问题的解空间进行编码，以便使得它能够由遗传算法进行操作。解码就是把遗传算法操作的个体转换成原来问题结构的过程。常见的编码方法有：二进制编码、浮点数编码、格雷码等。以二进制为例：假设某一参数的取值范围是[A，B]，A＜B，我们有长度为l的二进制编码串来表示该参数，将[A，B]等分成2l-1个子部分，每个等分的长度为δ，则它能够产生2l种不同的编码。
         00000000000…0000000000 = 0  →A
         00000000000…0000000001 = 1     →A + δ
         11111111111……1111111111 =→B
二进制编码的最大缺点是使得遗传算法操作的个体位串太长，这容易降低遗传算法的运行效率，很多问题采用其他编码方法可能更有利。如对于函数优化问题，浮点数编码方法就更有效，而二进制编码方法不但容易降低遗传算法的运行效率，而且会产生精度损失。浮点数编码方法是指个体的每个染色体用某一范围内的一个浮点数表示，个体的编码长度就等于问题变量的个数。
在实际运用遗传算法解决问题时，一般都需要根据具体的问题采用合适的编码方法，这样更有利于遗传算法搜索到问题的最优解。
（2）适应度函数
遗传算法在进化搜索中基本上不用外部信息，仅用目标函数也就是适应度函数为依据。适应度函数是用于度量问题中每一个染色体优劣程度的函数，体现了染色体的适应能力。遗传算法的目标函数不受连续可微的约束且定义域可以是任意集合。但对适应度函数有一个要求就是针对输入可以计算出的能加以比较的结果必须是非负的。
在具体应用中，适应度函数的设计要结合求解问题本身的要求而设计。因为适应度函数对个体的评估是遗传算法进行个体选择的唯一依据，因此适应度函数的设计直接影响到遗传算法的性能。对于很多问题，可以直接把求解问题的目标函数作为适应度函数使用，但也存在很多问题需要进行一定的转换才能使得目标函数可以用作遗传算法的适应度函数。
（3）遗传算子
遗传算法主要有三种操作算子：选择(selection)、交叉(crossover)、变异(mutation)。
○1选择算子
选择算子根据个体的适应度函数值所度量的优劣程度选择下一代个体。一般地，选择算子将使适应度函数值较大的个体有较大的机会被遗传到下一代，而适应度函数值较小的个体被遗传到下一代的机会较小。一般常采用的选择算子是赌轮选择机制。赌轮选择算子的基本原理如下。
令表示种群的适应度值之总和，表示群体中第i个染色体的适应度值，则第i个个体产生后代的能力正好为其适应度值与群体适应度值的比值。
赌轮选择算子在个体数不太多时，有可能出现不正确反映个体适应度的选择过程，也就是说适应度高的个体有可能反而被淘汰了。为了改进赌轮选择算子的这种缺点，有很多改进的交叉选择算子。如：最佳个体保存法、期望值方法、排序选择方法、联赛选择方法、排挤方法等。
○2交叉算子
在自然界生物进化过程中，起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中，起核心作用的是遗传操作的交叉算子。所谓交叉算子就是把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
交叉算子设计一般与所求解的具体问题有关，但都应该考虑以下两点：○A设计的交叉算子必须能保证前一代中优秀个体的性状能在后一代的新个体中尽可能得到遗传和继承。○B交叉算子与问题的编码是相互联系的，因此，交叉算子设计和编码设计需协调操作，也就是所谓的编码—交叉设计。
对于字符串编码的遗传算法，交叉算子主要有一点交叉、两点交叉、多点交叉和一致交叉等。其中一点交叉的主要操作过程如下。假设两个配对个体为P1、P2分别如下所示。经过一点交叉后，得到两个新的个体P1’、P2’。

对于实数编码的遗传算法，交叉算子主要是采用算术交叉算子。假设两个配对个体分别为P1＝(x1,y1)和P2=(x2,y2)。在P1和P2进行算术交叉后得到的两个新个体和分别可由下式计算得到。
      



○3变异算子
变异算子是改变数码串中某个位置上的数码。遗传算法中引入变异算子有两个目的：其一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解领域时，利用变异算子的这种局部随机搜索能力可以加速遗传算法向最优解收敛。一般在这种情况下，遗传算法的变异概率应取较小的值，否则接近最优解的积木块会因为变异而遭到破坏。其二是使遗传算法可以维持较好的群体多样性，以防止遗传算法出现未成熟收敛现象。此时，遗传算法的变异概率应取较大的值。
遗传算法中，交叉算子具有很好的全局搜索能力，是算法的主要操作算子。变异算子具有较好的局部搜索能力，是算法的辅助操作算子。遗传算法通过交叉和变异这一对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。变异算子除了基本的变异算子外，还有很多有效的变异算子。如逆转变异算子、自适应变异算子等。对于字符串编码的遗传算法，基本变异算子就是随机的从个体中选择某些基因位，然后以一定的概率对这些基因位进行翻转变异，也就是把这些基因位中为0的基因位以概率Pm变为1，为1的基因为以概率Pm变为0。对于实数编码的遗传算法，一般采用随机变异的方式，使变异个体的每一个变量分量加上一个随机数，一般使用均匀分布的随机数或者是高斯分布的随机数。
（4）基本遗传算法运行参数
N：群体大小，即群体中所含个体的数量，一般取20～100
T：遗传算法的终止进化代数，一般取100～500
pc：杂交概率，一般取0.4～0.99
pm：变异概率，一般取0.0001～0.1
pr：复制概率


三 实验仪器
macos
四 实验步骤/设计实现
设计估价函数
设计算法步骤
编写实验程序
五 实验代码


六 实验结果以及分析

实验四 候选消除算法
一 实验目的
熟悉和掌握示例学习的基本思想和基本方法，通过实验培养学生利用示例学习进行问题求解的基本技能。
先熟悉示例学习中常见算法的基本思想和流程；
用C、C++、JAVA或Prolog             语言编程实现实验内容。
利用所学的知识及实验结果，来完成实验报告的各项内容。


二 实验内容以及原理
示例学习(Learning from examples)又称为实例学习或从例子中学习，它是通过从环境中取得若干与某概念有关的例子，经归纳得出一般性概念的一种学习方法。在这种学习方法中，外部环境(教师)提供的是一组例子(正例和反例)，这些例子实际上是一组特殊的知识，每一个例子表达了仅适用于该例子的知识，示例学习就是要从这些特殊知识中归纳出适用于更大范围的一般性知识，它将覆盖所有的正例并排除所有反例。其任务是：给定函数f(未知)的实例集合，返回一个近似于f的函数h—h称为假设，所有h的集合称为假设空间。
Simon于1974年在一篇论文中，把从示例学习的问题描述为使用示教例子来指导对规则的搜索，并提出了两空间模型。



其中，实例空间模型为所有示教例子的集合。规则空间模型为所有规则的集合。两者的关系是：系统对实例空间的搜索完成实例选择，并将这些选中的活跃实例提交解释过程；解释过程对实例经过适当的转化，将这些实例变换为规则空间中的特定概念，以引导规则空间的搜索。
对实例空间而言示教例子的质量和实例空间的搜索是两个值得注意的问题：
（1）高质量的例子是无二义性的，它可以为规则空间的搜索提供可靠的指导；另外示教例子的排列次序也会影响学习。
（2）搜索实例空间的目的在于选择合适的例子，使得这些例子能证实或否定规则空间中假设的集合H。常见的搜索方法有：选择对划分规则空间最有利的实例；利用H中的假设过滤掉与那些期望为真的实例；选择新实例等。
对规则空间而言推理方法和规则表示是两个值得注意的问题：
（1）常见的归纳推理方法有：a.常量转化成变量；b.取消部分条件；c.放松条件；d.形成闭合区域；e.沿概念树上溯等。
（2）规则表示要注意：a.对规则的表示应适合归纳推理b.规则的表示与实例的表示一致；c.规则空间中应包含要求的规则。
常见的示例学习的算法有，寻找极大特殊假设法、候选消除算法、精练算子法、产生测试法等。这里我们主要介绍一下候选消除算法。
*候选消除算法
该方法以整个规则空间为初始的假设规则集合H。依据实例中的信息，系统对集合H进行一般化或特殊化处理，逐步缩小H。最后H收敛到只含有要求的规则。上述过程可称为H的变型过程，该过程主要是利用了H中规则与规则之间的偏序关系来进行规则的搜索。其算法如下：
（1）初始化G和S，G包含最一般假设，S包含最特殊假设。
（2）接受一个新的实例x，若x是正例，则从G中删除不包含x的概念，更新S，尽可能对S进行一般化以覆盖x；若x是反例，则从S中删除包含x的概念，更新G，尽可能对G进行特殊化使之不覆盖x。
（3）重复2，直到G=S
（4）输出G和S
如果G和S都为空，表示没有找到学习的概念描述;如果G和S相等且不为空，表示找到了学习的概念描述，且算法停止。


三 实验仪器
macOS
四 实验步骤/设计实现
设计估价函数
设计算法步骤
编写实验程序
五 实验代码

六 实验结果以及分析


部分源码：
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #include <iostream>

  7. typedef struct Chrom                           // 结构体类型，为单个染色体的结构；
  8. {
  9.         short int bit[6];//一共6bit来对染色体进行编码，其中1位为符号位。取值范围-64~+64
  10.         int fit ;//适应值
  11.         double rfit;//相对的fit值，即所占的百分比
  12.         double cfit;//积累概率
  13. }chrom;                                       
  14. //定义将会用到的几个函数；
  15. void *evpop (chrom popcurrent[4]);//进行种群的初始化
  16. int x (chrom popcurrent);
  17. int y (int x);
  18. void *pickchroms (chrom popcurrent[4]);//选择操作
  19. void *pickchroms_new (chrom popcurrent[4]); // 基于概率分布
  20. void *crossover (chrom popnext[4]);//交叉操作
  21. void *mutation (chrom popnext[4]);//突变
  22. double r8_uniform_ab ( double a, double b, int &seed );//生成a~b之间均匀分布的数字
  23. chrom popcurrent [4];                        // 初始种群规模为；
  24. chrom popnext [4];                           // 更新后种群规模仍为；
  25. void main ()                                    // 主函数；
  26. {
  27.         int num ;                                    // 迭代次数；
  28.         int i ,j, l,Max ,k;
  29.         Max=0;                                      // 函数最大值

  31.         printf("\nWelcome to the Genetic Algorithm！\n");  //
  32.         printf("The Algorithm is based on the function y = -x^2 + 5 to find the maximum value of the function.\n");

  34. enter:printf ("\nPlease enter the no. of iterations\n请输入您要设定的迭代数 : ");
  35.         scanf("%d" ,&num);                           // 输入迭代次数，传送给参数 num；

  37.         if(num <1)                                 
  38.                 goto enter ;                                 // 判断输入的迭代次数是否为负或零，是的话重新输入；
  39.         //不同的随机数可能结果不同？？那是当所设置的迭代次数过少时，染色体的基因型过早地陷入局部最优
  40.         srand(time(0));  
  41.         evpop(popcurrent );    // 随机产生初始种群；
  42.         //是否需要指定x的取值范围呢？6bit来表示数字，第一位为符号位，5bit表示数字大小。所以，取值范围为-32~+31
  43.         Max = popcurrent[0].fit;//对Max值进行初始化

  45.         for(i =0;i< num;i ++)                          // 开始迭代；
  46.         {

  48.                 printf("\ni = %d\n" ,i);                 // 输出当前迭代次数；

  50.                 for(j =0;j<4; j++)
  51.                 {
  52.                         popnext[j ]=popcurrent[ j];           // 更新种群；
  53.                 }

  55.                 pickchroms(popnext );                    // 挑选优秀个体；
  56.                 crossover(popnext );                     // 交叉得到新个体；
  57.                 mutation(popnext );                      // 变异得到新个体；

  59.                 for(j =0;j<4; j++)
  60.                 {
  61.                         popcurrent[j ]=popnext[ j];              // 种群更替；
  62.                 }

  64.         }  // 等待迭代终止；
  65. //对于真正随机数是需要注意取较大的迭代次数
  66.         for(l =0;l<3; l++)
  67.         {
  68.                 if(popcurrent [l]. fit > Max )
  69.                 {
  70.                         Max=popcurrent [l]. fit;
  71.                         k=x(popcurrent [l]);//此时的value即为所求的x值
  72.                 }

  74.         }
  75.         printf("\n 当x等于 %d时，函数得到最大值为： %d ",k ,Max);
  76.         printf("\nPress any key to end ! " );

  78.         flushall();                                 // 清除所有缓冲区；
  79.         getche();                                   // 从控制台取字符，不以回车为结束；

  81. }                                             



  85. void *evpop (chrom popcurrent[4])   // 函数：随机生成初始种群；
  86. {
  87.         int i ,j, value1;
  88.         int random ;
  89.         double sum=0;
  90.         
  91.         for(j =0;j<4; j++)                            // 从种群中的第1个染色体到第4个染色体
  92.         {
  93.                 for(i =0;i<6; i++)                       // 从染色体的第1个基因位到第6个基因位
  94.                 {
  95.                         random=rand ();                     // 产生一个随机值
  96.                         random=(random %2);                 // 随机产生0或者1
  97.                         popcurrent[j ].bit[ i]=random ;       // 随机产生染色体上每一个基因位的值，或；
  98.                 }  

  100.                 value1=x (popcurrent[ j]);                // 将二进制换算为十进制，得到一个整数值；
  101.                 popcurrent[j ].fit= y(value1); // 计算染色体的适应度值
  102.                 sum = sum + popcurrent[j ].fit;
  103.                 printf("\n popcurrent[%d]=%d%d%d%d%d%d  value=%d  fitness = %d",j, popcurrent[j ].bit[5], popcurrent[j ].bit[4], popcurrent[j ].bit[3], popcurrent[j ].bit[2], popcurrent[j ].bit[1], popcurrent[j ].bit[0], value1,popcurrent [j]. fit);
  104.                 // 输出整条染色体的编码情况，
  105.         }
  106.         //计算适应值得百分比，该参数是在用轮盘赌选择法时需要用到的
  107.         for (j = 0; j < 4; j++)
  108.         {
  109.                 popcurrent[j].rfit = popcurrent[j].fit/sum;
  110.                 popcurrent[j].cfit = 0;//将其初始化为0
  111.         }
  112.         return(0);               
  113. }                                       


  116. int x (chrom popcurrent)  // 函数：将二进制换算为十进制；
  117. {//此处的染色体长度为，其中个表示符号位
  118.         
  119.         int z ;
  120.         z=(popcurrent .bit[0]*1)+( popcurrent.bit [1]*2)+(popcurrent. bit[2]*4)+(popcurrent .bit[3]*8)+( popcurrent.bit [4]*16);

  122.         if(popcurrent .bit[5]==1)  // 考虑到符号；
  123.         {
  124.                 z=z *(-1);                             
  125.         }

  127.         return(z );                           
  128. }                                    
  129. //需要能能够从外部直接传输函数，加强鲁棒性
  130. int y (int x)// 函数：求个体的适应度；
  131. {
  132.         int y ;
  133.         y=-(x *x)+5;                                // 目标函数：y= - ( x^ 2 ) +5；
  134.         return(y );            
  135. }
  136. //基于轮盘赌选择方法，进行基因型的选择
  137. void *pickchroms_new (chrom popnext[4])//计算概率
  138. {
  139.         int men;
  140.         int i;int j;
  141.         double p;
  142.         double sum=0.0;
  143.         //find the total fitness of the population
  144.         for (men = 0; men < 4; men++ )
  145.         {
  146.                 sum = sum + popnext[men].fit;
  147.         }
  148.         //calculate the relative fitness of each member
  149.         for (men = 0; men < 4; men++ )
  150.         {
  151.                 popnext[men].rfit = popnext[men].fit / sum;
  152.         }
  153.         //calculate the cumulative fitness,即计算积累概率
  154.         popcurrent[0].cfit = popcurrent[0].rfit;
  155.         for ( men = 1; men < 4; men++)
  156.         {
  157.                 popnext[men].cfit = popnext[men-1].cfit + popnext[men].rfit;
  158.         }
  159.         
  160.         for ( i = 0; i < 4; i++ )
  161.         {//产生0~1之间的随机数
  162.                 //p = r8_uniform_ab ( 0, 1, seed );//通过函数生成0~1之间均匀分布的数字
  163.                 p =rand()%10;//
  164.                 p = p/10;
  165.                 if ( p < popnext[0].cfit )
  166.                 {
  167.                         popcurrent[i] = popnext[0];      
  168.                 }
  169.                 else
  170.                 {
  171.                         for ( j = 0; j < 4; j++ )
  172.                         {
  173.                                 if ( popnext[j].cfit <= p && p < popnext[j+1].cfit )
  174.                                 {
  175.                                         popcurrent[i] = popcurrent[j+1];
  176.                                 }
  177.                         }
  178.                 }
  179.         }
  180.         //  Overwrite the old population with the new one.
  181.         //
  182.         for ( i = 0; i < 4; i++ )
  183.         {
  184.                 popnext[i] = popcurrent[i];
  185.         }
  186.         return(0);
  187. }
  188. void *pickchroms (chrom popnext[4])          // 函数：选择个体；
  189. {
  190.         int i ,j;
  191.         chrom temp ;                                // 中间变量
  192.         //因此此处设计的是个个体，所以参数是
  193.         for(i =0;i<3; i++)                           // 根据个体适应度来排序；（冒泡法）
  194.         {
  195.                 for(j =0;j<3-i; j++)
  196.                 {
  197.                         if(popnext [j+1]. fit>popnext [j]. fit)
  198.                         {
  199.                                 temp=popnext [j+1];
  200.                                 popnext[j +1]=popnext[ j];
  201.                                 popnext[j ]=temp;

  203.                         }  
  204.                 }               
  205.         }
  206.         for(i =0;i<4; i++)
  207.         {
  208.                 printf("\nSorting:popnext[%d] fitness=%d" ,i, popnext[i ].fit);
  209.                 printf("\n" );                     
  210.         }
  211.         flushall();/* 清除所有缓冲区 */                     
  212.         return(0);
  213. }   
  214. double r8_uniform_ab( double a, double b, int &seed )
  215. {
  216.         {
  217.                 int i4_huge = 2147483647;
  218.                 int k;
  219.                 double value;

  221.                 if ( seed == 0 )
  222.                 {
  223.                         std::cerr << "\n";
  224.                         std::cerr << "R8_UNIFORM_AB - Fatal error!\n";
  225.                         std::cerr << "  Input value of SEED = 0.\n";
  226.                         exit ( 1 );
  227.                 }

  229.                 k = seed / 127773;

  231.                 seed = 16807 * ( seed - k * 127773 ) - k * 2836;

  233.                 if ( seed < 0 )
  234.                 {
  235.                         seed = seed + i4_huge;
  236.                 }

  238.                 value = ( double ) ( seed ) * 4.656612875E-10;

  240.                 value = a + ( b - a ) * value;

  242.                 return value;
  243.         }
  244. }
  245. void *crossover (chrom popnext[4])              // 函数：交叉操作；
  246. {

  248.         int random ;
  249.         int i ;
  250.         //srand(time(0));
  251.         random=rand ();                             // 随机产生交叉点；
  252.         random=((random %5)+1);                     // 交叉点控制在0到5之间；
  253.         for(i =0;i< random;i ++)                  
  254.         {
  255.                 popnext[2].bit [i]= popnext[0].bit [i];   // child 1 cross over
  256.                 popnext[3].bit [i]= popnext[1].bit [i];   // child 2 cross over
  257.         }

  259.         for(i =random; i<6;i ++)                      // crossing the bits beyond the cross point index
  260.         {
  261.                 popnext[2].bit [i]= popnext[1].bit [i];    // child 1 cross over
  262.                 popnext[3].bit [i]= popnext[0].bit [i];    // chlid 2 cross over
  263.         }  

  265.         for(i =0;i<4; i++)
  266.         {
  267.                 popnext[i ].fit= y(x (popnext[ i]));        // 为新个体计算适应度值；
  268.         }

  270.         for(i =0;i<4; i++)
  271.         {
  272.                 printf("\nCrossOver popnext[%d]=%d%d%d%d%d%d    value=%d    fitness = %d",i, popnext[i ].bit[5], popnext[i ].bit[4], popnext[i ].bit[3], popnext[i ].bit[2], popnext[i ].bit[1], popnext[i ].bit[0], x(popnext [i]), popnext[i ].fit);
  273.                 // 输出新个体；
  274.         }
  275.         return(0);
  276. ……………………

  278. …………限于本文篇幅 余下代码请从51黑下载附件…………
复制代码

全部资料51hei下载地址（内含完整源码）：
强彦.doc (712.88 KB, 下载次数: 14)
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表