第三章 遗传算法的理论基础 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland 的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。 3.1 模式定理 不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。 定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。 以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。 引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n 个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容 定义3.2 模式H 中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。 显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。 定义3.3 模式H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H δ。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。 模式的阶数和定义距描述了模式的基本性质。 下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令)(t A 表示第t 代中串的群体，以),,2,1)((n j t A j =表示第t 代中第j 个个体串。 1．选择算子 在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下： 设在第t 代种群)(t A 中模式所能匹配的样本数为m ，记为),(t H m 。在选择中，一个位串 j A 以概率/j j i P f f =∑被选中并进行复制，其中j f 是个体)(t A j 的适应度。假设一代中群体 大小为n ，且个体两两互不相同，则模式H 在第1+t 代中的样本数为：
实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)
遗传算法 遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。 比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解： 下续（表格） 下续……
即设有4个不同的初始特征组合，分别计算判别值，然后取最大的2个组合（[1,2,3,4,9]和[1,3,5,7,8]）进行杂交，即互换部分相异的特征（4和7），得到新的两个特征组合（[1,2,3,7,9]和[1,3,4,5,8]）,然后再计算这两个新的组合的判别值，和原来的放在一起，再从中选择2个具有最大判别值的组合进行杂交。如此循环下去，在某一代的时候就得到了一个最好的特征组合（比如第2代的[1,3,5,7,9]的特征组合）。当然，在实际中每代的个体和杂交的数量是比较大的。 遗传算法的具体的步骤如下：
1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验确定的。 2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规模而确定。 3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率( P)挑选的每两个父代 c 通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。
实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法(Genetic Algorithm —GA),就是模拟达尔文的遗传选择与自然淘汰的生物进化过程的计算模型，它就是由美国Michigan大学的J、Holla nd教授于1975 年首先提出的?遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位. 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算? 1. 遗传算法的基本原理 遗传算法的基本思想正就是基于模仿生物界遗传学的遗传过程?它把问题的参数用基因代表，把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体?这个群体在问题特定的环境里生存 竞争,适者有最好的机会生存与产生后代?后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境，不断进化,最后收敛到一族最适应环境的类似个体，即得到问题最优的解?值得注意的一点就是，现在的遗传算法就是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身就是否完全正确并不重要(目前生物界对此学说尚有争议). (1)遗传算法中的生物遗传学概念 由于遗传算法就是由进化论与遗传学机理而产生的直接搜索优化方法；故而 在这个算法中要用到各种进化与遗传学的概念? 首先给出遗传学概念、遗传算法概念与相应的数学概念三者之间的对应关系这些概念
（2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）:选择（Selection）、交叉（Crossover）、变异（Mutation）. 遗传算法基本步骤主要就是：先把问题的解表示成“染色体”，在算法中也就就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就就是假设的可行解.然后，把这些假设的可行解置于问题的“环境”中,并按适者生存的原则从中选 择出较适应环境的“染色体”进行复制 ，再通过交叉、变异过程产生更适 应环境的新一代“染色体”群.经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就就是问题的最优解. 下面给出遗传算法的具体步骤，流程图参见图1: 第一步:选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步:定义适应函数，便于计算适应值； 第三步:确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 第四步:随机产生初始化群体； 第五步:计算群体中的个体或染色体解码后的适应值； 第六步:按照遗传策略，运用选择、交叉与变异算子作用于群体，形成下一代群体； 第七步:判断群体性能就是否满足某一指标、或者就是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步. 图1 一个遗传算法的具体步骤
第十五课Arduino I/O函数 Arduino板上的引脚可以配置为输入或输出。我们将在这些模式下解释引脚的功能。重要的是要注意，大多数Arduino模拟引脚可以按照与数字引脚完全相同的方式进行配置和使用。 引脚配置为INPUT Arduino引脚默认配置为输入，因此在使用它们作为输入时，不需要使用 pinMode()显式声明为输入。以这种方式配置的引脚被称为处于高阻抗状态。输入引脚对采样电路的要求非常小，相当于引脚前面的100兆欧的串联电阻。 这意味着将输入引脚从一个状态切换到另一个状态所需的电流非常小。这使得引脚可用于诸如实现电容式触摸传感器或读取LED作为光电二极管的任务。 被配置为pinMode（pin，INPUT）的引脚（没有任何东西连接到它们，或者有连接到它们而未连接到其他电路的导线），报告引脚状态看似随机的变化，从环境中拾取电子噪音或电容耦合附近引脚的状态。 上拉电阻 如果没有输入，上拉电阻通常用于将输入引脚引导到已知状态。这可以通过在输入端添加上拉电阻（到5V）或下拉电阻（接地电阻）来实现。10K电阻对于上拉或下拉电阻来说是一个很好的值。 使用内置上拉电阻，引脚配置为输入 Atmega芯片内置了2万个上拉电阻，可通过软件访问。通过将pinMode()设置为INPUT_PULLUP可访问这些内置上拉电阻。这有效地反转了INPUT模式的行为，其中HIGH表示传感器关闭，LOW表示传感器开启。此上拉的值取决于所使用的微控制器。在大多数基于AVR的板上，该值保证在20kΩ和50kΩ之间。在Arduino Due上，它介于50kΩ和150kΩ之间。有关确切的值，请参考板上微控制器的数据表。 当将传感器连接到配置为INPUT_PULLUP的引脚时，另一端应接地。在简单开关的情况下，这会导致当开关打开时引脚变为高电平，当按下开关时引脚为低电平。上拉电阻提供足够的电流来点亮连接到被配置为输入的引脚的LED。如果项目中的LED似乎在工作，但很昏暗，这可能是发生了什么。 控制引脚是高电平还是低电平的相同寄存器（内部芯片存储器单元）控制上拉电阻。因此，当引脚处于INPUT模式时，配置为有上拉电阻导通的引脚将被开启；如果引脚通过
一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual
{ char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色
最近在看遗传算法,查了很多资料,所以做了如下一些总结,也希望对后面研究的人有些帮助.因为初学GA,文中自己的见解,不一定全对,感兴趣的可以一起探讨. I简介 基本概念 遗传算法(Genetic Algorithms, GA)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。 它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 GA的组成: （1）编码（产生初始种群） （2）适应度函数 （3）遗传算子（选择、交叉、变异） （4）运行参数 编码 基因在一定能够意义上包含了它所代表的问题的解。基因的编码方式有很多，这也取决于要解决的问题本身。常见的编码方式有： （1）二进制编码，基因用0或1表示（常用于解决01背包问题） 如：基因A：00100011010 (代表一个个体的染色体) （2）互换编码（用于解决排序问题，如旅行商问题和调度问题） 如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。 （3）树形编码（用于遗传规划中的演化编程或者表示）
如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。 编码方法：基因就是树形结构中的一些函数。 （4）值编码（二进制编码不好用时，解决复杂的数值问题） 在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。 适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 如TSP问题，遍历各城市路径之和越小越好，这样可以用可能的最大路径长度减去实际经过的路径长度，作为该问题的适应度函数。 遗传算子——选择 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。 SGA（基本遗传算法）中采用轮盘赌选择方法。 轮盘赌选择又称比例选择算子，基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为Fi，则个体i 被选中遗传到下一代群体的概率为： 遗传算子——交叉 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在GA中起关键作用，是产生新个体的主要方法。
——什么是Arduino/Arduino是什么 Arduino是一块简单、方便使用的通用GPIO接口板，并可以通过USB接口和电脑通信。 作为一块通用IO接口板，Arduino提供丰富的资源，包括： 13个数字IO口（DIO数字输入输出口）； 6个PWM输出（AOUT可做模拟输出口使用）； 5个模拟输入口（AIN模拟输入）。 Arduino开发使用java开发的编程环境，使用类c语言编程，并提供丰富的库函数。 Arduino可以和下列软件结合创作丰富多彩的互动作品：Flash，Processing，Max/MSP，VVVV…等。 Arduino也可以用独立的方式运作，开发电子互动作品，例如：开关控制Switch、传感器sensors输入、LED等显示器件、各种马达或其它输出装置。 下面是Arduino的硬件实物图片： Arduino实物图
——Arduino可以做什么 目前计算机的输入和输出设备，大家常见的、也是大家做熟悉的就是：键盘（输入）、鼠标（输入）、麦克（输入）和音响（输出）、显示器（输出）；对于一些玩游戏的朋友可能还包括游戏杆（输入），做音乐的可能还会接触到MIDI （输入）。 上述设备都很专业，功能也非常专一。你没办法让键盘给你唱歌，同样，你也没办法让音响替你输入文本。 Arduino更像是一种半成品，它提供通用的输入输出接口。你可以通过编程，把Arduino加工成你需要的输入输出设备。 你可以把Arduino做成键盘、鼠标、麦克等输入设备；你也可以把Arduino做成音响、显示器等输出设备。最重要的是，你可以把Arduino做成任何你希望的互动工具（输入和输出）。 如果你愿意，或者你需要，你完全可做使用Arduino开发出一个会唱歌的键盘或者一个让你的音响替你打字。（夸张的说法） 总之，Arduino是什么，是根据你的需求来确定的。你跟电脑之间的交互，从此插上了翅膀。
目录 _ 一、遗产算法的由来 (2) 二、遗传算法的国内外研究现状 (3) 三、遗传算法的特点 (5) 四、遗传算法的流程 (7) 五、遗传算法实例 (12) 六、遗传算法编程 (17) 七、总结 ......... 错误!未定义书签。附录一：运行程序.. (19)
遗传算法基本理论与实例 一、遗产算法的由来 遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。 遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的
A r d u i n o教程A r d u i n o 图形化编程软件 A r d u B l o c k Revised by Jack on December 14,2020
Arduino教程：Arduino图形化编程软件- ArduBlock 一款为Arduino设计的图形化编程软件，由上海新车间创客开发。ArduBlock软件是Arduino官方编程环境的第三方软件，目前必须依附于Arduino软件下运行，区别于Arduino文本式编程环境，ArduBlock是以图形化积木搭建的方式编程的，这样的方式会使编程的可视化和交互性加强，编程门槛降低，即使没有编程经验的人也可以尝试给Arduino控制器编写程序。 右图是图像编程，左图是生成的C语言，如果你不懂C语言，图形和中文你应该懂吧！
上图是一个led闪烁程序下面分析一下程序主程序do ->循环{设定1引脚输出高电平->延时1秒-> 设定1引脚输出低电平-> 延时1秒.}如果你是高手请回避：图形对应的C语言 void setup() { pinMode( 1 , OUTPUT); } void loop() { digitalWrite( 1 , HIGH ); delay( 1000 ); digitalWrite( 1 , LOW ); delay( 1000 ); } 兴致来了吧，马上安装。 下载地址： 先下载，打开，点击File，再点击Perferences（如图） 我们可以看到弹出的框，记住下面这个路径（如图） D:\我的文档\Arduino\tools\ArduBlockTool\tool进入看看你的文件夹有没有这个路径，如果没有就一直创建文件夹，然后把你下载回来的压缩包（其实是JAVA软件）复制在最后的文件夹里面，就安装完成了。
第二章遗传算法的基本原理 2.1遗传算法的基本描述 2.1.1全局优化问题 全局优化问题的定义：给定非空集合S作为搜索空间，f : S—>R为目标函数，全局优化问 题作为任务maxf（x）给出，即在搜索空间中找到至少一个使目标函数最大化的点。 X母 全局最大值（点）的定义：函数值f* = f（x*）::：■::称为一个全局最大值，当且仅当-X ? S= f（x）_ f（x ）成立时，x - S被称为一个全局最大值点（全局最大解）。 局部极大值与局部极大值点（解）的定义： 假设在S上给定了某个距离度量T，如果对x< S，； 0，使得对-S， ：：（X, X ）：：；= f（X）_ f（X ），则称x为一个局部极大值点，f （x '）为一个局部极大值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（multi-modalityfu nctio n ）。 主要考虑两类搜索空间： 伪布尔优化问题：当S为离散空间B L={0,1}L,即所有长度为L且取值为0或1的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。 连续参数优化问题：当取S伪n维实数空间R n中的有界集合S「「n=1［3i ,b i］，其中& ：：：b i，i =1,2, …，n时，相应的具有连续变量的优化问题称为连续参数优化问题。 对S为吐{0,1} L，常采用的度量时海明距离，当S「点［a i,bj时，常采用的度量就是欧氏距离。 2.1.2遗传算法的基本流程 遗传算法的基本步骤如下： 1）选择编码策略，把参数集合X和域转换为位串结构空间S; 2）定义适应度函数f（X）; 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P; 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。
第二章 遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f S x ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当x ? S x ∈，(ρi i b a <，i 12）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P ； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。
2.1.3 遗传编码 由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。 定义：由问题空间向GA 编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。 1）2）3）它们对1） 2） k =1,2,…,K; l =1,2,…,L; K=2L 其中，个体的向量表示为),,,(21kL k k k a a a a =，其字符串形式为kL k k k a a a s 21=，s k 称为个体a k 对应的位串。表示精度为)12/()(--=?L u v x 。 将个体又位串空间转换到问题空间的译码函数],[}1,0{:v u L →Γ的公式定义为： 对于n 维连续函数),,2,1](,[),,,,(),(21n i v u x x x x x x f i i i n =∈=，各维变量的二进制
摘要：基本遗传算法的操作是以个体为对象，只使用选择、交叉和变异遗传算子，遗传进化操作过程的简单框架。模式定理和积木块假设是解释遗传算法有效性的理论基础，理论分析与实际应用都表明基本的遗传算法不能处处收敛于全局最优解，因此基本遗传算法有待进一步改进。 关键词：遗传算法；遗传算法的改进 1.标准遗传算法 基本遗传算法包括选择、交叉和变异这些基本遗传算子。其数学模型可表示为： sag=（c，e，p0，n，φ，г，ψ，t） 其中c为个体的编码方法；e为个体适应度评价函数；p0为初始种群；n为种群大小；φ为选择算子；г为交叉算子；ψ为变异算子；t为遗传运算终止条件； 2 遗传算法基本方法及其改进 2.1编码方式 编码方式决定了个体的染色体排列形式，其好坏直接影响遗传算法中的选择算子、交叉算子和变异算子的运算，也决定了解码方式。 二进制编码 二进制编码使用的字符号{0，1}作为编码符号，即用一个{0，1}所组成的二进制符号串构成的个体基因型。二进制编码方法应用于遗传算法中有如下优点： 1）遗传算法中的遗传操作如交叉、变异很容易实现，且容易用生物遗传理论来解释； 2）算法可处理的模式多，增强了全局搜索能力； 3）便于编码、解码操作； 4）符合最小字符集编码原则； 5）并行处理能力较强。 二进制编码在存着连续函数离散化的映射误差，不能直接反应出所求问题的本身结构特征，不便于开发专门针对某类问题的遗传运算算子。 2.2初始种群的设定 基本遗传算法是按随机方法在可能解空间内产生一个一定规模的初始群体，然后从这个初始群体开始遗传操作，搜索最优解。初始种群的设定一般服从下列准则：1）根据优化问题，把握最优解所占空间在整个问题空间的分布范围，然后，在此分布范围内设定合适的初始群体。 2）先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。该过程不断迭代，直到初始群体中个体数目达到了预先确定的种群大小。 2.3选择算子的分析 选择算子的作用是选择优良基因参与遗传运算，目的是防止有用的遗传信息丢失，从而提高全局收敛效率。常用的遗传算子： （1）轮盘赌选择机制 轮盘赌选择也称适应度比例选择，是遗传算法中最基本的选择机制，每个个体被选择进入下一代的概率为这个个体的适应度值占全部个体适应度值之和的比例。但是轮盘赌选择机制选择误差较大，不是所有高适应度值的个体都能被选中，适应度值较低但具有优良基因模式的个体被选择的概率也很低，这样就会导致早熟现象的产生。 （2）最优保存选择机制 最优保存选择机制的基本思想是直接把群体中适应度最高的个体复制到下一代，而不进行配对交叉等遗传操作。具体步骤如下： 1）找出当前群体中适应度值最高和最低的个体的集合；
遗传算法（GENETIC ALGORITHM，GA） 一、遗传算法的特点： 1、遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有多条，而非单条，因而具有良好的并行性。 2、遗传算法只需要利用目标的取值信息，而无需梯度等高价值信息，因而适用于任何大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。 3、遗传算法择优机制是一种软选择，加上其良好的并行性，使它具有良好的全局优化和稳健性。 4、遗传算法操作的可行解是经过编码化的（通常采用二进制编码），目标函数解释为编码化个体（可行解）的适应值，因而具有良好的可操作性和简单性。 二、遗传算法的发展与现状 遗传算法的产生归功于美国的Michigan大学的Holland在20世纪60年代末、70年代初的开创性，其本意是在人工适应系统中设计的一种基于自然演化原理搜索机制。大约在同一时代，Foegl和Rechenberg及Schwefel,引入了另两种基于自然演化原理的算法，演化程序（evolutionary programming）和演化策略(evolution strategies).这三种算法构成了目前演化计算(evolutionary computation)领域的三大分支，它们从不同层次、不同角度模拟自然演化原理，以达到求解问题的目的。Holland不仅设计了遗传算法的模拟与操作原理，更重要的是他运用统计策略理论对遗传算法的搜索机理进行了理论分析，
建立了著名的Schema定理和隐含并行（implicit parallelism）原理，为遗传算法奠定了基础。遗传算法应用于函数优化始于De Jone的在线（one-line）和离线（off-line）指标仍是目前衡量遗传算法性能的主要手段。 1、遗传算法在神经网络、模糊系统和机器学习中的应用 神经网络的学习包含两个优化过程，分别是网络连接权重的优化和网络拓扑结构的优化。优化连接权重最著名的方法是Rumelhart提出的基于梯度下降法的反向传播法（backpropagation,BP）。BP算法的最大弱点是局部极小问题和无法学习网络拓扑结构。作为一种通用性和全局性良好的优化技术，遗传算法用于神经网络的训练就是很自然的事情。遗传算法用于神经网络的学习可分为三个不同的层次：连接权重的学习规则的学习。目前遗传算法已经广泛用于前向网络（feedward networks）、径向基网络（radial basis function networks）、Kohonen特征映射及Recurrent网络等各种人工神经网络的训练与设计中。演化神经网络（evolutionary artificial neural networks）作为一种一般的自适应学习模型加以研究。 被Zedeh 称作软计算（soft computing）的两大组成部分——遗传算法与模糊系统的相互融合也是近年人们关注的话题。模糊系统是对人类处理模糊性概念极其推理机制的模拟。最初，在模糊系统设计中，推理方法的选取、隶属函数形状及参数的选取、相关权重的确定以及规则的确定，均是由专家根据实际经验经验指定的。模糊神经网络（fuzzy neural networks）.遗传算法已成功应用于隶属函数形状与参
Arduino 教程一 数字输出 教程一:
Arduino, 教程 11 Comments ?
Arduino 的数字 I/O 被分成两个部分，其中每个部分都包含有 6 个可用的 I/O 管脚，即管脚 2 到管脚 7 和管脚 8 到管脚 13。除了管脚 13 上接了一个 1K 的电阻之外，其他各个管脚都直接连接到 ATmega 上。我们可以利用一个 6 位的数字跑马灯，来对 Arduino 数字 I/O 的输出功能进行验证，以下是相应的原理图： 电路中在每个 I/O 管脚上加的那个 1K 电阻被称为限流电阻， 由于发光二极管在电路中没有等效电阻值， 使用限流电阻可 以使元件上通过的电流不至于过大，能够起到保护的作用。 该工程对应的代码为：
int BASE = 2; int NUM = 6; int index = 0; void setup() { for (int i = BASE; i < BASE + NUM; i ++) { pinMode(i, OUTPUT); } } void loop() { for (int i = BASE; i < BASE + NUM; i ++) { digitalWrite(i, LOW); } digitalWrite(BASE + index, HIGH); index = (index + 1) % NUM; delay(100); }
下载并运行该工程，连接在 Arduino 数字 I/O 管脚 2 到管脚 7 上的发光二极管会依次点亮 0.1 秒，然后再熄灭：
1
这个实验可以用来验证数字 I/O 输出的正确性。Arduino 上一共有十二个数字 I/O 管脚，我们可以用同样的办法验证其他六个管脚的正 确性，而这只需要对上述工程的第一行做相应的修改就可以了：
int BASE = 8;
SEP
01
Arduino 教程二 数字输入 教程二:
Arduino, 教程 3 Comments ?
在数字电路中开关（switch）是一种基本的输入形式，它的作用是保持电路的连接或者断开。Arduino 从数字 I/O 管脚上只能读出高电 平（5V）或者低电平（0V），因此我们首先面临到的一个问题就是如何将开关的开/断状态转变成 Arduino 能够读取的高/低电平。解 决的办法是通过上/下拉电阻，按照电路的不同通常又可以分为正逻辑（Positive Logic）和负逻辑（Inverted Logic）两种。 在正逻辑电路中，开关一端接电源，另一端则通过一个 10K 的下拉电阻接地，输入信号从开关和电阻间引出。当开关断开的时候， 输入信号被电阻“拉”向地，形成低电平（0V）；当开关接通的时候，输入信号直接与电源相连，形成高电平。对于经常用到的按压式 开关来讲，就是按下为高，抬起为低。 在负逻辑电路中，开关一端接地，另一端则通过一个 10K 的上拉电阻接电源，输入信号同样也是从开关 和电阻间引出。当开关断开时，输入信号被电阻“拉” 向电源，形成高电平（5V）；当开关接通的时候，输 入信号直接与地相连，形成低电平。对于经常用到的 按压式开关来讲，就是按下为低，抬起为高。 为了验证 Arduino 数字 I/O 的输入功能，我们可以将 开关接在 Arduino 的任意一个数字 I/O 管脚上（13 除 外），并通过读取它的接通或者断开状态，来控制其 它数字 I/O 管脚的高低。本实验采用的原理图如下所 示，其中开关接在数字 I/O 的 7 号管脚上，被控的发 光二极管接在数字 I/O 的 13 号管脚上：
Arduino 教程三 模拟输入 教程三:
Arduino, 教程 5 Comments ?
2
基本遗传算法及应用举例 遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。 针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。 1．1．1 编码方法 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L 为一固定的数，如 X=1010100 表示一个个体，该个体的染色体长度L=20。 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a ，b]，我们用长度为L 的二进制编码符号串来表示该参数，总共能产生L 2种不同的编码，若参数与编码的对应关系为 00000000000……00000000=0 →a 00000000000……00000001=1 →a+δ ? ? ? ……=L 2-1→b 则二进制编码的编码精度1 2--= L a b δ 假设某一个个体的编码是kl k k k a a a x 21=，则对应的解码公式为 )2(121 ∑=---+=L j j L kj L k a a b a x 例如，对于x ∈[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串：
遗传算法的基本原理和方法 一、编码 编码：把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。 解码（译码）：遗传算法解空间向问题空间的转换。 二进制编码的缺点是汉明悬崖（Hamming Cliff），就是在某些相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变都难以跨越。 格雷码（Gray Code）：在相邻整数之间汉明距离都为1。 （较好）有意义的积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积木块；最小字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或描述。 二进制编码比十进制编码搜索能力强，但不能保持群体稳定性。 动态参数编码（Dynamic Paremeter Coding）：为了得到很高的精度，让遗传算法从很粗糙的精度开始收敛，当遗传算法找到一个区域后，就将搜索现在在这个区域，重新编码，重新启动，重复这一过程，直到达到要求的精度为止。 编码方法：
1、二进制编码方法 缺点：存在着连续函数离散化时的映射误差。不能直接反映出所求问题的本身结构特征，不便于开发针对问题的专门知识的遗传运算算子，很难满足积木块编码原则 2、格雷码编码：连续的两个整数所对应的编码之间仅仅只有一个码位是不同的，其余码位都相同。 3、浮点数编码方法：个体的每个基因值用某一范围内的某个浮点数来表示，个体的编码长度等于其决策变量的位数。 4、各参数级联编码：对含有多个变量的个体进行编码的方法。通常将各个参数分别以某种编码方法进行编码，然后再将他们的编码按照一定顺序连接在一起就组成了表示全部参数的个体编码。 5、多参数交叉编码：将各个参数中起主要作用的码位集中在一起，这样它们就不易于被遗传算子破坏掉。评估编码的三个规范：完备性、健全性、非冗余性。 二、选择 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。 常用的选择算子： 1、轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。