简述遗传算法的基本原理篇1
关键词：故障诊断；遗传算法；神经网络；小波分析
引言
遗传算法Ga（Geneticalgorithms）模拟了达尔文的“适者生存，优胜劣汰”的自然进化论与孟德尔的遗传变异理论是由michigan大学Holland教授1975年在他的专著adaptationinnaturalandartificial首次提出。其基本流程如图1。遗传算法（Ga）与传统算法有很多不同之处，主要体现在Ga适应性强，其使用的算子是随机的，如交叉、变异和繁殖等算子不受确定性规则的控制。但这种搜索也不是盲目的，而是向全局最优解方向前进。直接使用适值函数进行适值计算，而不需要求优化函数的导数，使一些不可求导的优化函数也可用Ga优化；Ga具有较强的鲁棒性，它能同时搜索解空间的多个点，从而使之收敛于全局最优解，而不至于陷入局部最优解；另外它还具有智能性和并行性，利用遗传算法的方法，可以解决那些结构尚无人能理解的复杂问题。它已广泛应用于函数优化、组合优化、模式识别和信号处理等领域，在处理复杂优化问题时遗传算法显示了巨大潜力，在实际工程应用中取得了巨大成功。由于上述特点，建立合理的模型，可以将Ga用于设备的状态监测和故障诊断之中。本文把近年来的有关Ga用于故障诊断的文献进行分析、归纳，总结出Ga在故障诊断中的具体应用。
Ga用于故障诊断从目前来看，有直接应用于故障诊断之中，主要用于提取特征向量，为诊断的后续处理作准备。有和其他的诊断方法相结合，研究得较多。
一、利用遗传算法提取、优化特征参数
机械故障诊断是一个典型的模式分类问题。在诊断实践中，由于诊断对象的复杂性，故障特征和故障类别的对应关系不甚明了，人们提出了大量的原始特征以进行故障识别。但由于特征向量之间存在一定的关联性，且特征向量对不同故障的敏感程度不同，这对设备诊断的效率和准确率有重要的影响。要对这些特征向量进行优化，使它们能够适应实际需要。
史东锋等对回转机械故障诊断中3类由同步振动引起的故障来分析，应用遗传算法，染色体采用二进制编码方式，以样本类内、类间的距离判据为适应值函数，进行特征选择，高效地剔除原始特征集的冗余特性，提高故障的识别精度。而用常规方法对得到的23个特征量进行分类，由于起高度的冗余性，很难取得理想的分类效果。
二、遗传算法与人工神经网络（ann）的结合应用
人工神经网络以其强有力的学习和并行处理能力为故障诊断提供了全新的理论方法和实现手段。神经网络通过对经验样本的学习，将知识以权值和阈值的形式存储在网络中。网络的输入是被诊断对象的征兆即特征值，输出则表示发生故障的可能性。神经网络是以神经元为信息处理的基本单元，以神经元间的连接弧为信息通道，多个神经元联结而成的网络结构。神经网络以其独特的联想、记忆和学习功能在机械设备故障诊断领域受到广泛关注，其中研究较多的是Bp神经网络及其改进算法。
三、遗传算法与模糊集理论的结合应用
模糊集理论是一种新的数据分析和处理方法，使用模糊集理论可以对决策表进行简化，去除冗余属性。故障模糊诊断的基本原理是利用模糊变换的原理、最大隶属度和阈值原则，根据各故障的原因与征兆之间不同程度的因果关系，在综合考虑所有征兆基础上来诊断旋转机械振动故障的可能原因。将模糊集理论应用到解决旋转机械故障诊断问题时，要计算旋转机械振动故障数据库中的频域征兆，使用模糊集理论对其进行约简，根据约简的结果生成规则。利用得到的规则对故障样例进行诊断。
四、遗传算法与小波理论的结合应用
小波变换作为新的信号处理手段，具有传统傅立叶变换和加窗傅立叶变换无法比拟的优点。其特点是实现了对信号的多分辨率分析，便于对信号的总体和局部进行刻划；且能将信号准确还原。利用它对信号的分解和重构特性，可有针对性地选取有关频带的信息和剔除、降低噪声干扰，这对于机械故障诊断具有很大的实际意义。
简述遗传算法的基本原理篇2
关键词:免疫遗传算法tSp初始种群优化
1引言
遗传算法(Geneticalgorithm,简称Ga)[1]是一种常用的大规模并行搜索优化算法,它模拟了达了达尔文“适者生存”的规律和随机信息交换思想,仿效生物的遗传方式。从随机生成的初始解群出发,采用选择、交叉、变异等算子进行操作,产生优于父代的子代,如此循环执行,使优化过程以大概率趋于全局最优。但其本身还存在许多不足,尤其在解群分布不均匀时易出现末成熟收敛,陷入局部极优,其原因在于Ga中基于适应度的多样性保持策略没能保持群体的多样性。
为了解决上述问题,文献[2-5]提出了使遗传算法具有免疫功能的免疫遗传算法。其算法一般包括六大块组成:抗原的识别,初始抗体的产生,适应度计算,向记忆细胞分化,抗体的促进和抑制,抗体产生(选择,交叉,变异)。
免疫遗传算法既保留了遗传算法的搜索待性,克服了遗传算法在局部搜索解空间上效率较差的缺点,又在很大程度上避免末成熟收敛。但由于其每一代种群的产生仍只通过简单的遗传算子(选择,交叉,变异)产生,收敛效果不是很理想,因此,本文提出了一种针对上述情况的用于tSp(travelingSalesmanproblem,旅行商问题)的改进免疫算法。文中首先描述用于tSp寻优问题的改进免疫算法的实现过程,然后通过对tSp问题测试数据进行仿真。仿真结果说明该算法收敛速度快,较易实现。
2旅行商问题(tSp)
travelingsalesmanprolem(tSp)问题是经典的np难问题,是典型的组合优化问题,具有很强的应用背景,例如,ViSi芯片设计,路径优化,网络路由,机器人控制等许多问题都可以建模为tSp问题。tSp问题其核心思想就是要寻找一条遍历L个城市的最短路径,在数学上可以描述为以下优化问题
其中,C为城市集合,为城市编号,i=1,2,3,……,,为编号i和j的两城市之间的距离。
3用于tSp的改进免疫算法描述
3.1基本概念
抗原:算法中的抗原一般是指城市之间的距离距阵,及其约束条件(距离最小)
抗体:算法中的抗体一般是指生成的各个路径
抗体与抗体之间的亲合度:用于表明抗体之间的相似度,本文采用基于信息熵的亲合度计算[5],即:
式中为抗体之间亲合度,为抗体u与v的平均信息量
抗体与抗原之间的亲合度:用于表明抗体对抗原的识别程度,本算法中抗体与抗原的亲合度定义为:最长路径值和抗体的路径长度值之差及其与所有差值和之比
式中为城市个数,为城市距离中最大两城市之间的距离,为存在的可能最大路径值
式中表示抗体与抗原之间的亲合度,表示路径的长度值。
3.2算法描述与算法步骤
如果把实际求解问题的城市距离视为外来入侵的抗原,那么,免疫响应中产生的抗体视为问题的解,则不同亲和度抗体的进化与成熟机制就是寻找最优路径(路径值最短)。本文的改进算法主要是针对传统的遗传算法以及文献[9]所使用的基于信息熵的免疫遗算法的收敛效率问题所提出来的。算法采用实数编码,减少二进制编码的计算量,提高了搜索的效率;引入抗体群优化策略,可以在初始或经遗传算子进化生成的种群中提高抗体与搞原的亲合度,从而提高算法的搜索效率。
本文算法的主要步骤如下:
步骤1:算法初始化:抗原输入及参数的设定:输入城市坐标值(或随机生成坐标值),并通过欧几里得距离计算公式:
计算抗原值;
同时设定种群规模n,相似度阈值γ,交叉率pm,变异率pc;
步骤2:抗体的编码:抗体的编码采用实数编码,抗体的长度为n(城市的个数)
步骤3:产生初始抗体群,记忆库:先检查记忆库,如果为空则在可可行解空间随机产生初始抗体群,否则,从记忆库中选择和随机产生的其余抗体共同组成初始抗体群。
步骤4:抗体种群的优化:由于tSp问题的任何一条路径都是闭合路径,则从任一城市出发,要到达的下一个城市选择为未到过的城市中距离该城市最近的一个,这样更能使种群朝着有利方向收敛。
步骤5:对上述抗体群体进行评估:计算抗体与抗原适应度值及各抗体的浓度值,
以个体选择率为标准进行评估。定义选择率为,,式中,表示抗体与抗原的亲合度,表示抗体的浓度。抗体的浓度是指抗体群体中相似抗体所占的比重,即:=与抗体i相似度大于γ的抗体数/n;
步骤6:将抗体种群基于选择率进行选择操作,再对选择出的抗体实施交叉、变异操作。
步骤7:记忆优良个体:计算变异后的抗体群体的亲和度,选择高亲和度的抗体,加入记忆细胞库。
步骤8:终止条件判断:判断是否满足终止条件;是则算法结束;否则返回步骤4.
步骤9:输出最优路径。
4仿真实验及分析
为了测试本文算法的性能并和相关算法进行比较,本文分别选用国际上通用的tSp测试库中的eil51-cities和Berlin52-cities数据为例进行测试[6]。
相关参数:种群数目n:100,交叉率pc=0.7变异率pm=0.1,相似度阈值γ=0.02
方法一:遗传算法;
方法二:文(5)中所提的基于信息熵的免疫遗传算法;
方法三:本文方法;
其运行的结果如下列图:
在相同参数设置下,从图1中我们看到在100次迭代次数以内,本文算法算法具有较快的收敛性,从图2中我们看到虽然最终三种算法都能求得最优解,但采用不同的算法,收敛速度不同,而本文的算法明显优于Ga与iGa,其在170代左右就能求得最优解,而Ga与iGa由分别需650代与340代左右。综合上述仿真实验结果可知:本文提出的用于tSp优化路径与相关算法比较,它能够在较少的迭代代数下,求出最优解,加快点收敛的效率。
5结语
本文是基于生物免疫系统机制,在文[5](基于信息熵的免疫算法)的基础上,提出了一种改进的用于tSp路径优化的免疫遗传算法。文中详细的讨论了该算法的步骤和过程,最后对两测试数据包进行了实验仿真,并和相关算法进行了比较,初步仿真实验结果表明:本文提出的算法应该有效的,值得进一步研究和应用于实际复杂问题的优化计算中。
参考文献
[1]云庆夏编著.进化算法[m].北京:冶金工业出版社,2ooo-05.
[2]高岩,位耀光,付冬梅,张蔚.免疫遗传算法的研究及其在函数优化中的应用.《微计算机信息》,2007,23(6):183～184.
[3]杨孔雨,王秀峰.免疫记忆遗传算法信其完全收敛性研究.计算机工程与应用,2005,12:47～50.
[4]JiaoLC,wangL.anovelgeneticalgorithmbasedimmunity.ieeetransactionsonSystemman,andCybernetics,2000,30(5):552~561
[5]杨四海,tSp的等价解及其对免疫遗传算法的干扰.华侨大学学报(自然科学版)1期,2007年1月.
简述遗传算法的基本原理篇3
关键词：遗传算法；tSp；编码；算子；变异
中图分类号：tp301文献标识码：a文章编号：1009-3044(2011)26-6488-03
theResearchofSolvingtSpBasedonGeneticalgorithm
wanGKe
(JinhuatobaccoCompanyYongkangBranch,Jinhua321300,China)
abstract:thepaperfocusesontheapplicationresearchofgeneticalgorithms,ithascompletedthefollowingtwoaspectsofthework:1)First,makingthenecessarygeneticalgorithmtheoryexpounded,discussingtheimplementationofgeneticalgorithmintheapplicationdevelopment;presentedadescriptionofthealgorithmrealizationofthesimpleprocessinClanguage;2)themainapplicationsandthelatestresearchareasofgeneticalgorithmsarebrieflydescribed;describedtheoriginalmethodtosolvethetSp,discussedtheapplicationthatgeneticalgorithmsolvedtSpintheencodedrepresentationandgeneticoperationoperatorsandotheraspects.
Keywords:geneticalgorithm;travellingsalesmanproblem;encode;operator;mutation
遗传算法（Geneticalgorithm，简称Ga）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。与传统的搜索算法(基于微分的搜索技术、枚举技术、和随机搜索技术)相比，遗传算法适合于非连续或非处处可微、非凸、多峰和带噪音等复杂优化问题的求解，在复杂问题求解中有着显著的优势[1]。
我们习惯上把Holland1975年提出的Ga称为传统的Ga。它的主要步骤包括编码、初始群体的生成、适应性值评估检测、选择、交叉、变异。遗传算法的一般结构可描述如下：
begin
t0;
初始化p(t);
评估p(t);
while不满足终止条件do
begin
重组p(t)获得C(t);
评估C(t);
从p(t)和C(t)中选择p(t+1);
tt+1;
end
end
1用遗传算法来解决巡回旅行商问题
巡回旅行商问题（travellingSalesmanproblem，简称tSp），也称为货郎担问题，是一个较古老的问题。几十年来出现了很多近似优化算法，如近邻法（nearestneighbor）、贪心算法（greedyalgorithm）、最近插入法（nearestinsertion）、最远插入法（farthestinsertion）、双极小生成树法（doubleminimumspanningtree）等等。近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法、模拟退火方法以及遗传算法方法[2]。
1.1tSp问题的描述与建模
tSp问题可以简单地描述成：已知n个城市之间的相互距离，现有一推销员必须遍访这n个城市，并且每个城市只能访问一次，最后有必须返回出发城市。如何安排她对这些城市的访问次序，可使其旅行路线的总长度最短？其数学描述如下：设有一城市集合C=｛C1,C2,…,Cn｝。其每对城市Ci,Cj∈C间的距离为d(Ci,Cj)∈Z+。求一条经过C中每个城市正好一次的路径(Cπ(1),Cπ(2),…,Cπ(n))，使得
(1)
最小。这里(π(1),π(2),…,π(n))是(1,2,…,n)的一个置换。若采用图论语言，tSp问题还可描述为：
设G=(V,a)是一个图，此处V是具有n个顶点的集合，a称为弧或边集；D=(d0)是与a关联的距离或费用矩阵。tSp就是要决定一条经过所有顶点正好一次(这样的回路称为一条路径或Hami1ton回路)且距离最短的回路。若对任意i,j∈V有dij=dji，则该问题称为对称的tSp；否则称为非对称tSp。若对任意的i,j,k∈V有dij+djk≥dik，则称费用矩阵满足三角不等式。当V∈R2且dij为i和j间的直线距离时，该问题称为平面（或euclid）tSp问题。此类问题的费用矩阵满足三角不等式。
非对称旅行商问题较难解，在本文中介绍利用遗传算法求解对称旅行商问题的方法[3]。
若对于城市V={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2，t3,…,tn)，其中ti∈V(i=1,2,3，…,n)，且记tn+1=t1，则旅行商问题的数学模型为：
(2)
1.2对tSp的遗传基因编码
在旅行商问题的各种求解方法中，描述旅行路线的方法主要有如下两类：
1)巡回旅行商路线所经过的连接两个城市的路线顺序排列；
2)巡回旅行路线所经过的各个城市的顺序排列。
大多数求解旅行商问题的遗传算法是一后者为描述方法的，它们都采用所遍历城市的顺序排列来表示各个个体的编码串，其等位基因为n个整数值或n个记号。
用遗传算法求解tSp问题，算法设计的重点在编码的表示，即回路的编码和遗传算子的设计方面。tSp的编码主要包括二进制表示、近邻（adjacency）表示、次序（ordinal）表示、路径（path）表示、矩阵表示和边（edge）表示等。由于二进制表示不自然且需要额外的修正算子以保证个体的合法性，在实际中很少使用。路径表示自然、直观，且易于加入启发式信息，是用得最多的一种表示策略[4]。
tSp搜索空间随着城市数n的增加而增大，所有的旅程路线组合数为(n-1)!/2。5个城市的情形对应120/10=12条路线，10个城市的情形对应3628800/20=181440条路线，100个城市的情形则对应有4.6663×10155条路线。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的计算困难。借助遗传算法的搜索能力解决tSp问题，是很自然的想法。但如果将一条旅程路线表示为一个n城市的排列，基于二进制编码的交叉和变异操作就不能适用，所以需要重新设计遗传操作，以适应这类遗传基因表示问题。
1.3操作算子的设计与分析
1)顺序表示
假定讲旅行商问题中所有城市所组成的一个列表记为w，给每个城市分配一个1～n之间的序号，将这个序号的排列也表示为w，即：
w=(v1,v2,v3,v4,v5,…,vn)
w=(12345…n)
用编码串:
t：12345678…n
来表示这样的一个城市遍历路线：从城市v1开始，依次经过城市v2、v3、v4、v5、…、vn，然后再返回到出发城市v1。
对于一个旅行商问题的城市列表w，假定对各个城市的一个访问顺序为t，t=(t1，t2，t3，…,tn),规定每访问完一个城市，就从城市列表w中将该城市去掉，则用第i（i=1,2,3,…,n）个所访问的城市ti在所有未访问城市列表就可表示具体访问哪个城市，如此这样直到处理完w中所有的城市。将全部gi顺序列在一起所得到的一个列表G=(g1g2g3…gn)就可以表示一条巡回路线，它即为一个个体基因。
2)交叉算子的设计
旅行商问题对交叉算子的设计要求是：对任意两条巡回路线进行交叉操作之后，都能够得到另外两条新的并且具有实际意义的巡回路线。过去10年里，为换位表达设计了好几种交叉算子，如部分映射交叉（pmX）、顺序交叉（oX）、循环交叉（CX）、基于位置的交叉、基于顺序的交叉、启发式交叉等。
3)变异算子的设计
旅行商问题对变异算子的设计要求是：对任意一个个体编码串进行变异操作后，所产生的新个体应该能对应于一条具有实际意义的巡回路线。如点位变异、逆转变异、对换变异、插入变异算子
2.4基于遗传算法求解tSp问题的实现
现就基本的遗传算法框架，简要介绍其算法实现过程[4]。
2.4.1编码与适应度函数
我们以n城市的遍历次序作为遗传算法的编码，由于在可行解群体的初始化、交叉操作及变异操作中均隐含tSp问题的合法性约束条件。故适应度函数取为哈密尔顿圈的长度的倒数(无惩罚函数)。
2.4.2选择机制
开始，我们用随机方法产生初始化群。随着遗传算法的执行，我们保留m个较优的个体作为样本群体，以供选择；在每一代运算过程中，个体被选中的概率与其在群体中的相对适应度成正比。
2.4.3交叉方法
我们选用的交叉方法与oX法有点类似，现介绍如下：
1)随机在串中选择一个区域，如两父串及区域选定为：
a＝12|3456|789
B＝98|7654|321
2)将B的区域加到a的前面或后面，a的区域加到B的前面或后面得到：
a'＝765|4123456789
B'＝3456|987654321
3)在a'中自支配区域后依次删除与区相同的城市码、得到最终的两子串为：
a"＝765412389
B"＝34569872l
与其它方法相比，这种方法在两父串相同的情况下仍能产生一定程度的变异效果，这对维持群体内一定的多样化特性有一定的作用，实验中也显示了较好的结果。
2.4.4变异技术
由于在选择机制中采用保留最佳样本方式，为保持群体内个体的多样化，我们采取连续多次对换的变异技术，使可行解有较大的顺序排列上的变比。变异操作发生的概率取得比较小(1％左右)，一旦变异操作发生，则用随机方法产生交换次数K，对所需变异操作的串进行K次对换(对换的两码位也是随机产生的)。
2.4.5“进化逆转”操作
引入“进化逆转”操作的主要目的是改善遗传算法的局部搜索能力。在针对tSp问题的遗传算法中，“逆转”是一种常见的“变异”技术。我们使用的“进化逆转”是一种单方向的(朝着改进的方向)和连续多次的“逆转”操作，即对于给定的串，若“逆转”使串(可行解)的适应度提高，则执行逆转操作．如此反复，直至不存在这佯的逆转操作为止。这一操作实际上使给定的串改良到它的局部极点，这种局部爬山能力与基本遗传其法的全局搜索能力相结合在实验中显示了较好的效果。
3结论
按照上述算法编制的，群体规模定为100，交叉概率为0.95。变异概率为0.003，初始可行解群体由随机产生。结果表明：
1)当n≤15时，随机样本实验表明，本算法可100％搜索到用穷举法求得的最优解。
2)当15≤30时，我们对组样本进行了测试，结果表明本算法能收敛到一稳定的“最好解”（难以确认其最优性）；多次实验的误差结果为0。
鉴于tSp问题的特点，许多方法只能解决小规模tSp[5]。处理大规模tSp的一个自然的想法是：把整个网络分成若干区和层次，每个层次中的每个区作为一个小规模tSp，用现有算法求解；再把每一层视为每一区作为一点的又一个小规模tSp，如此逐区逐层求解；最后按某种区、层连接原则连接各区和层，便可得到大规模tSp的一个次优解。分区分层法的关链在于：①如何分区分层；②各区、层如何连接；③小规模问题采用何种算法。Sa法在n
参考文献：
[1]ansarin,Houputationalintelligenceforoptimization[m].Boston:Kluweracademicpublishers,1997.
[2]mitchellm.anintroductiontogeneticalgorithms[m].Cambridge,ma:themitpress,1996.
[3]KernighanBw,pickeR.thepracticeofprogramming[m].ma:addison-wesleyLongmaninc,1999.
简述遗传算法的基本原理篇4
关键词：遗传算法，混沌，图像分割
0引言
遗传算法是一种全局优化搜索算法，它使用了群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而产生新的一代种群，并逐渐使种群进化到包含最优解或近似最优解的状态。近几年来借助于混沌改进遗传算法的性能是遗传算法领域研究的热点之一，遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力，搜索精度，搜索速度等几方面得到较明显的改进。
1混沌的特征和虫口方程
混沌是存在于非线形系统中的一种较为普遍的现象，具有遍历性、随机性等特点，混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，无疑会比随机搜索更具有优越性。科技论文。
描述生态学上的虫口模型Logistic映射自may于1976年开始研究以来，受到了非线形科学家的高度关注，Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型，如下式所示：
2混沌遗传算法
基于混沌遗传算法的二维最大熵算法基本步骤如下：
1.设置混沌遗传算法的种群规模以及最大进化代数；
2.生成初始群体。随机产生S和t,其中,S,t∈(0,1)。然后利用式
计算每个个体的适应值。式（2-1）中的s和t分别由以下公式确定：s=(int)(S*255)，t=(int)(t*255)。对初始种群执行混沌扰动，如果在C1步之内找到更优个体，则替换原来的个体，否则保留原个体。科技论文。混沌扰动方式按式(1-1)进行。
3.如果当前进化代数大于G，转步骤5，否则执行变异操作。变异方式按如下公式进行：
其中，fRandom()产生（0,1）之间的随机数，如果变异后的个体具有更优的适应值,则把该个体加入当前种群；
4.执行混沌操作。如果在C2步之内找到更优解,则替代原来的个体,否则保留原个体。混沌扰动按公式(1-1)进行。结束后转步骤6。
5.在较小范围内执行混沌扰动。扰动方式：
其中m1,m2为混沌变量，且m1,m2∈（0,1）。如果变异后的个体具有更优的适应值,则替换原来的个体,否则保留原个体。
6.按规定的种群规模直接选择最优个体进入下一代。
7.如果满足终止条件,返回最优解,否则从步骤3重复上述过程。
8.利用最优解分割图像。
3实验结果与分析
为了检验本算法的效果，用文中提出的基于混沌遗传算法（以下简称为B算法）和基于传统遗传算法的二维最大熵算法（以下简称为a算法）对Couple.bmp图像进行了实验比较。科技论文。当文中算法和基于传统遗传算法的二维最大熵算法中各取最大进化代数为10时,分割效果如图3、4所示。
图1Couple原图图2Couple图像直方图
图3a算法结果图图4B算法结果图
4结论
混沌遗传算法是混沌思想与遗传算法思想的结合，比传统遗传算法具有更好的群体多样性、更强的全局寻优能力。文中将混沌遗传算法与二维最大熵图像分割算法结合，应用于图像分割，对比于基于传统遗传算法的二维最大熵算法，文中算法具有更强的稳定性,更快的执行速度，分割效果好。
参考文献
[1]吴薇，邓秋霞，何曰光．基于免疫遗传算法的图像阈值分割．纺织高校基础科学学报，2004，17(2)：160-163
[2]薛景浩，章毓晋，林行刚．二维遗传算法用于图像动态分割．自动化学报，2000，26(5)：685-689
[3]王小平，曹立明．遗传算法－理论、应用与软件实现．西安交通大学出版社．2002
简述遗传算法的基本原理篇5
摘要文章对数据挖掘中软计算方法及应用作了综述。对模糊逻辑、遗传算法、神经网络、粗集等软计算方法，以及它们的混合算法的特点进行了分析，并对它们在数据挖掘中的应用进行了分类。关键词数据挖掘；软计算；模糊逻辑；遗传算法；神经网络；粗集1引言在过去的数十年中，随着计算机软件和硬件的发展，我们产生和收集数据的能力已经迅速提高。许多领域的大量数据集中或分布的存储在数据库中[1][2]，这些领域包括商业、金融投资业、生产制造业、医疗卫生、科学研究，以及全球信息系统的万维网。数据存储量的增长速度是惊人的。大量的、未加工的数据很难直接产生效益。这些数据的真正价值在于从中找出有用的信息以供决策支持。在许多领域，数据分析都采用传统的手工处理方法。一些分析软件在统计技术的帮助下可将数据汇总，并生成报表。随着数据量和多维数据的进一步增加，高达109的数据库和103的多维数据库已越来越普遍。没有强有力的工具，理解它们已经远远超出了人的能力。所有这些显示我们需要智能的数据分析工具，从大量的数据中发现有用的知识。数据挖掘技术应运而生。数据挖掘就是指从数据库中发现知识的过程。包括存储和处理数据，选择处理大量数据集的算法、解释结果、使结果可视化。整个过程中支持人机交互的模式[3]。数据挖掘从许多交叉学科中得到发展，并有很好的前景。这些学科包括数据库技术、机器学习、人工智能、模式识别、统计学、模糊推理、专家系统、数据可视化、空间数据分析和高性能计算等。数据挖掘综合以上领域的理论、算法和方法，已成功应用在超市、金融、银行[4]、生产企业[5]和电信，并有很好的表现。软计算是能够处理现实环境中一种或多种复杂信息的方法集合。软计算的指导原则是开发利用那些不精确性、不确定性和部分真实数据的容忍技术，以获得易处理、鲁棒性好、低求解成本和更好地与实际融合的性能。通常，软计算试图寻找对精确的或不精确表述问题的近似解[6]。它是创建计算智能系统的有效工具。软计算包括模糊集、神经网络、遗传算法和粗集理论。2数据挖掘中的软计算方法目前，已有多种软计算方法被应用于数据挖掘系统中，来处理一些具有挑战性的问题。软计算方法主要包括模糊逻辑、神经网络、遗传算法和粗糙集等。这些方法各具优势，它们是互补的而非竞争的，与传统的数据分析技术相比，它能使系统更加智能化，有更好的可理解性，且成本更低。下面主要对各种软计算方法及其混合算法做系统性的阐述，并着重强调它们在数据挖掘中的应用情况。2.1 模糊逻辑模糊逻辑是1965年由泽德引入的，它为处理不确定和不精确的问题提供了一种数学工具。模糊逻辑是最早、应用最广泛的软计算方法，模糊集技术在数据挖掘领域也占有重要地位。从数据库中挖掘知识主要考虑的是发现有兴趣的模式并以简洁、可理解的方式描述出来。模糊集可以对系统中的数据进行约简和过滤，提供了在高抽象层处理的便利。同时，数据挖掘中的数据分析经常面对多种类型的数据，即符号数据和数字数据。nauck[7]研究了新的算法，可以从同时包含符号数据和数字数据中生成混合模糊规则。数据挖掘中模糊逻辑主要应用于以下几个方面：（1）聚类。将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。聚类分析是一种重要的人类行为，通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的关系。模糊集有很强的搜索能力，它对发现的结构感兴趣，这会帮助发现定性或半定性数据的依赖度。在数据挖掘中，这种能力可以帮助阻止搜到无用和微不足道的知识。研究者为此发展了模糊聚类算法，并得到了广泛应用[8]。在高维数据挖掘中有太多的属性要考虑，因此知识简约就非常的必要。属性聚类的实质就是知识简约，所谓知识约简，就是在保持知识库的分类或者决策能力不变的条件下，删除不重要的或冗余的知识，最小约简（含有最小属性）是人们所期望的，且约简结果是不确定的。所以模糊聚类成为知识简约的有力工具。（2）关联规则。数据挖掘重要的一点是关联规则的发现，关联规则挖掘是寻找给定数据集中属性间的关联。其中，布尔关联规则考虑的是关联的属性在与不在的二维特征，概化关联规则描述的是属性的分层关系，量化关联规则描述的是量化的属性（既离散化的属性）间的关联[9]。由于使用模糊概念表示的规则更符合人的思维和表达习惯，增强了规则的可理解性，所以模糊技术已成为数据挖掘系统中的关键技术。文献[10]中用模糊分类开拓了概化关联规则。（3）数据概化。概化发现是数据挖掘重要部分之一。它将大的数据集从较低的概念层抽象到较高的概念层，用可理解的信息来表达数据库中最重要的部分，并提供给用户。大数据集的语言概化通过有效的程度来获得，参考的标准内容在挖掘任务中。系统由概述、一致性程度真实和有效性组成。已经发现的最有兴趣的语言概化并不琐碎，却很人性化。实际上，它并不能自动地进行概化，需要人的操作。kacprzyk和zadrozny[11]发展了功能依赖度，语言概化使用了自然和可理解性的词汇，它支持模糊元素，包括属性间模糊的、重要的相互作用。首先，用户必须制定概化兴趣度，然后系统从数据库中获得记录，并计算每个概化的有效性，最后，选择最适合的语言概化。此方法通过网络浏览器已用在因特网上。模糊值、模糊联系和语言量都通过java来定义。（4）web应用。通过web日志的挖掘，来发现用户访问web页面的模式。通过分析web日志记录中的规律，可以识别电子商务的潜在客户，增强对最终用户的internet信息服务的质量和交付，并改进web服务器系统的性能。还可以进一步获得用户访问的附加信息（包括web服务器缓冲区中用户浏览web页面的序列等），以便于做更为详细的web日志分析。如通过用户访问模式的学习改进其自身的web站点，有助于建立针对个体用户的定制web服务。为了挖掘出较完全的兴趣模式,吴瑞[12]提出一种新的结构类型--flaat,它可发现那些被忽略的用户浏览偏爱路径。同时引进模糊集来处理停留在网页上的时间,以形成语义术语使挖掘出的用户浏览偏爱路径更自然、更易理解。算法能准确地反映用户的浏览兴趣。（5）图像检索。随着近来由多种媒体数据构成的多媒体信息仓库数据的增加，基于内容的图像检索开始活跃在这个领域。和传统数据库中基于精确匹配的关键字来检索信息不同，基于内容的图像检索系统的信息是一个图像的可视特征。如颜色、纹理、形状等。由于检索中查询要求往往是根据人的主观性所决定，因此很大程度上带有模糊性。对于图像纹理，习惯于用“很粗”、“中等”、“弱”这样的一些模糊概念来描述；形状一般用“几何形的”、“立体形的”或“似长方形的”、“正方形的”等概念描述；颜色特征通常用“很艳”、“一般”、“暗淡”或“大红”、“紫红”、“红”这样的模糊概念来描述。所以基于内容是图像检索是基于图像的相似特征来检索的。2.2神经网络数据挖掘的困难主要存在于三个方面：首先，巨量数据集的性质往往非常复杂，非线性、时序性与噪音普遍存在；其次，数据分析的目标具有多样性，而复杂目标无论在表述还是在处理上均与领域知识有关；第三，在复杂目标下，对巨量数据集的分析，目前还没有现成的且满足可计算条件的一般性理论与方法。研究者们主要是将符号型机器学习方法与数据库技术相结合，但由于真实世界的数据关系相当复杂，非线性程度相当高，而且普遍存在着噪音数据，因此这些方法在很多场合都不适用。因为神经网络的黑箱问题，在数据挖掘的初期并不看好，然而，神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和高度容错等特性，以及它对未经训练的数据分类模式的能力，非常适合解决数据挖掘中存在的以上问题，因此近年来越来越受到人们的关注。规则抽取方法是解决“黑箱问题”的有效手段。神经网络规则抽取的研究最早开始于80年代末。1988年，gallant[13]设计了一个可以用if-then规则解释推理结论的神经网络专家系统。根据设计思想的不同，目前的规则提取方法大致可以分成两大类，即基于结构分析的方法和基于性能分析的方法。基于结构分析的神经网络规则抽取方法把规则抽取视为一个搜索过程，其基本思想是把已训练好的神经网络结构映射成对应的规则。由于搜索过程的计算复杂度和神经网络输入分量之间呈指数级关系，当输入分量很多时，会出现组合爆炸。因此，此类算法一般采用剪枝聚类等方法来减少网络中的连接以降低计算复杂度。rx算法[14]首先用权衰减方法构造bp网络（该网络中连接权的大小反映了连接的重要程度），然后对网络进行修剪，在预测精度不变的情况下删除次要连接，在对网络进行充分简化的条件下，对隐藏层结点的激活值进行聚类，根据不同的隐藏层结点激活值用穷举搜索的办法来寻找从输入层到隐藏层和从隐藏层到输出层的规则.与基于结构分析的方法不同，基于性能分析的神经网络规则抽取方法并不对神经网络结构进行分析和搜索，而是把神经网络作为一个整体来处理，这类方法更注重的是抽取出的规则在功能上对网络的重现能力，即产生一组可以替代原网络的规则。较有代表性的算法是sestito等人提出的相似权值法[15]，这种方法将输出节点添加到输入层去与输入节点进行比较。1994年，craven和shavlik[16]为神经网络规则抽取任务下了一个定义：给定一个训练好的神经网络以及用于其训练的训练集，为网络产生一个简洁而精确的符号描述。在文献[16]的基础上，1996年，craven和shavlik[17]提出了trepan算法。该算法首先用训练好的神经网络对示例集进行分类，然后将该集合作为训练集提供给决策树学习算法，从而构造出一棵与原网络功能接近的、使用mofn表达式作为内部划分的决策树。trepan的计算量较低。1997年，craven和shavlik[18]将trepan用于一个噪音时序任务，即美元?马克汇率预测，取得了比现有方法更好的效果。2.3 遗传算法遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。它是美国michigan大学的holland教授于1975年首先提出的。遗传算法中包含了5个基本要素：①参数编码；②初始群体的设定；③适应度函数的设计；④遗传操作设计；⑤控制参数设定。遗传算法具有十分顽强的鲁棒性、自适应性，其在解决大空间、多峰值、非线性、全局优化等复杂度高的问题时具有独特的优势。因此，遗传算法在数据挖掘技术越来越显示出其重要的地位。数据挖掘最初应用进化计算从给定的目标集中挖掘有趣
的规则[19]，其强调从面向对象的数据库中发现数据集的共有特性。遗传算法也应用于其他方面如从多媒体数据库中挖掘多媒体数据。遗传算法在数据挖掘中主要应用于数据回归和关联规则的发现。(1)回归。除了发现可解释的模式之外，数据挖掘的另外一个重要的任务就是预测，即通过数据库中的一些变量发掘其超未来的趋势值。传统的线性回归需要先假设这些属性间没有相关性，而遗传算法则可以很好的处理有相关性的变量。xu[20]曾设计了一个多输入单输出的系统，应用遗传算法从训练数据集中进行非线性多元回归。(2)关联规则。遗传学习首先创建一个由随机产生的规则组成的初始群体。每个规则可以用一个二进制位串表示的if-than类型。通过全局搜索，形成由当前群体中最适合的规则组成新的群体。遗传算法可以单独用于数据仓库中关联规则的挖掘，还可以和其他的数据挖掘技术相结合，例如，用于进化神经网络结构以得到结构简单、性能优良的神经网络结构[21]；用于特征子集选择[22]；应用于决策树、分类器和模糊规则的获取等等。2.4 粗集粗集理论由波兰逻辑学家pawlak教授在20世纪80年代提出，是一种处理含糊和不确定问题的新型数学工具。粗集理念基于给定训练数据内部的等价类的建立。给定现实世界数据，通常有些类不能被可用的属性区分。粗集可以用来近似定义这种类，将问题的数据集进行划分，然后对划分的每一部分确定其对某一概念的支持程度：即肯定支持此概念，肯定不支持此概念，并分别用下近似和上近似集合来表示为正域、负域。它能有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识和潜在的规律。同时，粗集理论在处理大数据量，消除冗余信息等方面有着良好的效果，因此广泛应用于数据挖掘的数据预处理、规则生成等方面。(1)数据约简。粗集理论可提供有效方法用于对信息系统中的数据进行约简在数据挖掘系统的预处理阶段，通过粗集理论删除数据中的冗余信息（属性、对象以及属性值等），可大大提高系统的运算速度。文献[23]使用粗集方法对信息系统进行属性及属性域的约简，然后使用神经网络对约简后的数据进行分类，从而在网络分类精度没有明显下降的前提下使网络的学习速度提高到约简前的4.72倍。(2)规则抽取。与其它方法（如神经网络）相比，使用粗集理论生成规则是相对简单和直接的，信息系统中的每一个对象既对应一条规则。粗集方法生成规则的一般步骤为：①得到条件属性的一个约简，删去冗余属性；②册去每条规则的冗余属性值；③对剩余规则进行合并目前己经产生了许多基于粗集理论的方法用于从信息系统中抽取规则[24］。粗集理论存在对错误描述的确定性机制过于简单，而且在约简的过程中缺乏交互验证功能，因此，粗集理论与其它方法如神经网络、遗传算法、模糊数学、决策树等相结合可以发挥各自的优势，大大增强数据挖掘的效率。文献[25]提出了一种融合粗集理论和神经网络的数据挖掘新方法，应用于大型数据库的分类规则挖掘。其主要思想是首先由粗糙集理论对数据库进行初步约简，然后借助于神经网络在自学习过程中完成对数据库的进一步属性约简，并过滤数据中的噪声数据，最后由粗糙集理论对约简后的数据库进行规则抽取。粗集理论的使用提高了系统的运算速度，同时神经网络则使产生的规则集泛化能力提高。2.5 混合方法综合软计算的主要算法可产生在并行化、容错、自适应性和不定性管理方面更好的系统。混合系统可使许多应用中的自动化自适应系统成为现实。模糊系统的推理能力，当与神经网络和遗传算法的学习能力结合时，导致得到体现合理有效的认识系统（可学习和推理的系统）的新产品和新过程。banerjee[25]利用粗糙集、神经网络和模糊逻辑相结合的方法设计了数据挖掘系统，其中用粗糙集方法在决策表中进行约简。而用模糊集方法挖掘出未经加工的知识，最后由神经网络根据依赖度进行取舍。3结束语目前，数据挖掘中算法和可视化的研究越来越显得重要。因为从数据库中很容易就可以发现大量的模式，而这些模式中很多是很显而易见的、冗余的、无用的，或是对用户来说没有趣的。现在就需要能够过滤这些模式而提供给用户有用或有趣的模式的挖掘技术。软计算方法包括模糊逻辑、神经网络、遗传算法、粗集和混合方法近来用于解决这些问题。软计算具有以低求解成本、快速的方法解决复杂问题。本文对数据挖掘中软计算方法及应用作了一个综合性阐述。对它们的特点进行了分析，并对它们在数据挖掘中的应用进行了分类。模糊集为这个过程中的处理不确定性提供了一个自然框架，神经网络和粗集广泛应用于分类和规则生成。遗传算法应用于各种优化和搜索过程中，如优化排序和模式选择。参考文献[1]u.fayyadandr.uthurusamy,“dataminingandknowledgediscoveryindatabases,”commun.acm,vol.39,pp.24?27,1996.[2]w.h.inmon,“thedatawarehouseanddatamining,”commun.acm,vol.39,pp.49?50,1996.[3]杨会志.数据挖掘技术的主要方法及其发展方向.河北科技大学学报[j]．2000，21（3）：77-80．[4]j.a.majorandd.r.riedinger,“efd—ahybridknowledgestatisticalbased工作systemforthedetectionoffraud,”int.j.intell.syst.,vol.7,pp.687?703,1992.[5]r.heider,troubleshootingcfm56-3enginesfortheboeing737—usingcbranddata-mining,spinger-verlag,newyork,vol.1168,pp.512?523,1996.lecturenotesincomputerscience.[6]zadehl．，fuzzvlogic，neuralnetworkandsoftcomputing．communicationsoftheacm，1994,37(3)：77-84．[7]d.nauck,“usingsymbolicdatainneuro-fuzzyclassification,”inproc.nafips99,newyork,june1999,pp.536?540.[8]汤效琴，戴汝源.数据挖掘中变量聚类方法的应用研究.计算机工程与应用[j].2004，40（24）：171-173.[9]范明,孟小峰译.数据挖掘：概念与技术[m].北京：机械工业出版社，2001.[10]q.weiandg.chen,“mininggeneralizedassociationruleswithfuzzytaxonomicstructures,”inproc.nafips99,newyork,june1999,pp.477?481.[11]j.kacprzykands.zadrozny,“dataminingvialinguisticsummariesofdata:aninteractiveapproach,”inproc.iizuka98,fukuoka,japan,oct.1998,pp.668?671.[12]吴瑞．基于flaat模糊的web挖掘算法．武汉科技大学学报（自然科学版）[j].2005,28（3）：270-272.[13]s.i.gallant.neuralneworklearningandexpertsystems.cambridge,ma:mitpress,1993.[14]rudysetiono,liuh.understandingneuralnetworksviaruleextraction.in:procofthe14thinternationaljointconferenceonartificialintelligence,montreal,1995.pp.480-485[15]sestitos,dillont.knowledgeacquisitionofconjunctiverulesusingmultilayeredneuralnetworks.internationaljournalofintellsys,1993,8(7):779～805[16]m.w.craven,j,w,shavlik.usingsamplingandqueriestoextractrulesfromtrainedneuralnetworks.in:procofthe7thint'lconfonmathinelearning,newbrunswick,1994.pp.37～45[17]m.w.craven,j,w,shavlik.extractingtree-structuredrepresentationsoftrainednetworks.cambridge,ma:mitpress,1996.[18]m.w.craven,j,w,shavlik.usingneuralnetworksindatamining.futuregenerationcomputersystems.1997.13.pp.211-229.[19]t.ryuandc.f.eick,“masson:discoveringcommonaltiesincollectionofobjectsusinggeneticprogramming,”inproc.1stannu.conf.geneticprogramming1996,stanforduniv.,ca,july28?31,1996,pp.200?208.[20]k.xu,z.wang,andk.s.leung,“usinganewtypeofnonlinearintegralformultiregression:anapplicationofevolutionaryalgorithmsindatamining,”proc.ieeeint.conf.syst.,man,cybern.,pp.2326?2331,oct.1998.[21]郑志军，林霞光.一种基于神经网络的数据挖掘方法.西安建筑科技大学学报[j].2000，32[22]刘勇国，李学明，张伟基.于遗传算法的特征子集选择.计算机工程[j].2003，29[23]jelonekj，krawieck.roughsetreductionofattributesandtheirdomainsforneuralnetworks［j］.computationalintelligence．1995．11（2）：339－347.[24]kryszkiewiczm.rulesinincompletesystems[j].informationsciences,1999,113(4):271-292.[25]banerjeem.palk.roughfuzzymlp:knowledgeencodingandclassification[j].ieeetrans.neuralnetworks,2002.9:1203-1216.
简述遗传算法的基本原理篇6
（泰安职业技术学院财经系，山东泰安271000）
摘要：将粗集－遗传支持向量机模型运用到供应链绩效评价中，首先利用粗集理论剔除影响供应链绩效评价的冗余因素，获得核心影响因素，再采用支持向量机对于提取得到的核心影响因素预测供应链绩效所处的级别。在支持向量机分类过程中，利用遗传算法对支持向量机算法的参数进行寻优，获得最佳参数模型，而后预测得到供应链绩效评价级别。最后，实例运用此模型进行了预测，并与只运用粗集－支持向量机进行预测的结果进行对比。结果表明，利用粗集－遗传支持向量机方法对供应链绩效评价级别的预测准确率更高，预测结果更符合实际，是一种科学可行的方法。
关键词：供应链；绩效评价；粗集理论；支持向量机；遗传算法
中图分类号：tp18文献标识码：a文章编号：0439－8114（2015）03－0733-05
随着经济全球化，企业的经营环境发生了巨大的变化。越来越多的企业管理者已经意识到，未来的企业竞争将是供应链（SupplyChain，简称SC）与供应链之间的竞争，而不是企业之间的竞争。企业为了在市场竞争中始终处于有利地位，获得长期竞争优势及利益，就必须建立高效、安全、可靠的供应链系统，供应链系统可以各种辅助手段实现其一体化过程。
所谓供应链是指将产品和服务提供给最终消费者的所有环节的企业所构成的上下游产业一体化的体系。供应链管理是从系统的观点出发，通过对采购、制造、分销直至消费者的整个过程中的资金流、物流、信息流的协调，通过此种管理模式来满足消费者的要求及需求。然而只有对供应链系统中的各成员供应链绩效评价理论及其重要性的认识统一，才能让他们将对整个供应链系统的贡献度作为自己的考核目标，并将这些具体指标达成情况作为利益分配及任务分配的依据，如此才能使供应链的整体绩效切实得到提高。目前，将粗集－遗传支持向量机（Ga－SVm）方法应用到供应链绩效评价领域的研究并不多见，本研究主要利用粗糙集理论剔除供应链绩效评价的冗余因素及指标，提取获得影响供应链绩效评价的核心因素，再运用对于小样本具有良好泛化能力的支持向量机来进行评价，支持向量机的评价过程中通过遗传算法来进行相关参数寻优操作［1，2］。
1粗集理论
波兰学者pawlak于1982年提出了粗糙集（RoughSet）理论，粗糙集理论就是在无需提供问题需要处理数据之外的任何其他先知信息，而是仅根据已知的数据剔除冗余信息，获得本质信息，分析得到知识的不完整程度，生成决策或分类的相关规则及准则，实现通过分类准则或规则对已知数据进行精简或约减，对于处理未确知和模糊数据具有良好的效果［3－5］。
1．1信息系统
一个信息系统S通过下式表示：S＝（U，a，V，f），其中U为论域，（U＝｛x1，x2，……，xn｝）由有限个研究对象组成；a＝C∪D为属性集，其中C是条件属性集，D是决策属性集；V是值域；f是映射，对a∈a，x∈U，实现关于属性a的值。
1．2不可区分关系
粗糙集理论将知识和分类紧密联系起来，知识是对客观数据进行分类的能力，分类就是将差别的数据对象分析成为一类，它们之间的关系称之为不可分辨关系或等价关系，其中知识库可以用K＝（U，R）表示，其中U是非空有限集，称之为论域，R是U上的一族等价关系。UΠR为R的所有等价类族。［X］R表示包含元素x∈U的R的等价类。若yypR且p≠?椎，则p中全部等价关系的交集也是一种等价关系，称为p上的不可区分关系，记为ind（p），
1．3属性约简与核
定义1：假设S＝（U，R）为信息系统，R是U上的等价关系族，x∈R，若U／inD（R）＝U／inD（R－r），则称是R中可以被约简掉的知识，否则不可被约简掉。
定义2：对于任意r∈p（pR），若其中的p都是不可被约简的，则其等价关系族p是独立的，否则认为p是相关的。
定义3：假定S＝（U，R）为信息系统，如果子族pR满足下列条件：inD（p）＝inD（R），而且p是独立的，则称p是R的一个约简。
如果p是R的约简，则p必须满足以下条件：①p独立；②p与R有相同的分类能力，即inD（p）＝inD（R）。
定义4：假定S＝（U，R）为信息系统，如果其中R不可约去的属性，则称做R是核属性，所有核属性构成的集合称为核集，记作Core（R），称Core（R）为R的核。
1．4粗集的上、下近似及边界
定义1：给定知识库K＝（U，R），XU，称y（X）＝｛x｜［x］RX，x∈U｝为集合X的下近似，也称（X）是X的R正域，记做poSR（X）；显然，X的R正域poSR（X）是由U中完全属于X的元素构成的集合。（X）是一个确定性集合，它是由完全包含在X中的那些R的等价类（中的元素）构成的集合。即X的R正域poSR（X）中的元素可被正确分类。
定义2：称BnR（X）＝（X）－（X）为X的R边界域，称neGR（X）＝U－（X）为X的负域。显见，负域中的元素由不能确定是否属于X的元素组成。
1．5决策表的简化
对于决策表的条件属性进行化简，也就是对决策表的简化，简化的决策表具有与之前的决策表相同的决策等功能，不影响其核心功能的体现，只不过是简化后的决策表具有更少的条件属性，这样会提高决策和评价效率。因此，决策表的简化在实际应用领域中占有相当分量。换言之，在更少的条件下，获得同样的决策，使得利用一些相对之前更为简单的手段或条件就可以获得同样的决策或结果。决策表的简化步骤如下：（1）对决策表的条件属性进行约简，获得核心因素，也就是消去决策表中的某些列；（2）约简掉决策表中重复的某些行消去重复的行；（3）约简掉属性的冗余值。
本研究主要通过以上3个步骤对决策表进行属性约简，以期得到影响供应链绩效评价的主要因素或指标，约简掉冗余因素或指标，为下一步的供应链支持向量机评价奠定一个良好的基础。
2遗传－支持向量机回归模型
2．1支持向量机基本原理
SVm是基于结构风险最小化原则的方法，由于其是一个凸二次优化问题，从而保证能找到一个全局最优解，而且其能够较好地解决小样本、非线性、高维数等实际问题，问题的复杂程度不再简单地取决于维数高低，并且具有良好的泛化能力［6－8］。对于其凸二次优化问题，可以应用标准的拉格朗日乘子法进行优化求解。
假设训练样本为｛（x1，y1），……（xi，yi）｝，其中（xi∈Rm）是第i个学习样本的输入值，且为m维列向量，yi∈R为对应的目标值。可以建立如下形式的回归函数：
式（1）中，｛｝表示内积运算，wi描述了函数fi（t）的复杂度，bi为常数。考虑到函数的复杂度和拟合误差，函数拟合问题等价于满足如下约束条件时
最小化代价泛函
式（3）中，C为惩罚因子，?孜i为松弛变量。对于这个寻优问题，可以建立以下函数
式（4）中，（αi）l为Lagrange乘子。考察式（2）所给函数极值存在条件，可以获得求解所有参数的一个方程组，并最终得到回归函数（1）的表达式为
式（5）中，Ki（t，tl）为满足mercer条件的支持向量机核函数。广泛应用一种核函数为径向基核函数
式（6）中，i为xi的标准偏差。
当每个训练数据所对应的回归函数fi（t）均被确定后，可以得到回归函数为
支持向量机回归模型中具有多个参数，易陷入局部最优，因此本研究利用具有全局寻优能力的遗传算法对其参数进行寻优。
2．2遗传算法基本原理
遗传算法和传统搜索算法不同，它首先随机产生一组初始解，即“种群（population）”，种群中的每一个个体，即问题的一个解向量，称为“染色体（Chromosome）”，开始搜索过程。这些染色体在后续迭代中不断进化，生成的下一代染色体称为“后代（offspring）”。每一代中染色体的好坏可通过染色体的适应值（Fitness）来评价：适应值大的染色体被选择的几率高，相反，适应值小的染色体被选择的可能性小，被选择的染色体通过交叉（Crossover）和变异（mutation）产生新的染色体，即后代；经过若干代之后，算法收敛于最好的染色体，该染色体很可能就是问题的最优解或近似最优解。遗传算法的运行步骤如下［9－15］：（1）随机产生初始种群popk；（2）以适应度函数对染色体进行评价；（3）按适应值高低选择染色体形成新种群newpopk；（4）通过交叉、变异操作产生新的染色体即后代offspring；（5）不断重复步骤（2）－（4），直到获得预定进化代数。
其迭代流程见图1所示。由上述步骤可看出，遗传算法主要由遗传运算（交叉和变异）和进化运算（选择）组成。
交叉运算是最主要的遗传运算，遗传算法的性能在很大程度上取决于所采用的交叉运算的性能。交叉运算同时对两个染色体操作，组合两者的特性产生新的后代。变异则是一种基本运算，它在染色体上自发产生随机变化。变异可以提供初始种群中不含有的基因，或找回选择过程中丢失的基因，为种群提供新的内容。
3实证分析
设计任何评价指标体系都应遵循一些基本原则，因此，本研究结合供应链绩效评价的概念，根据目的性原则、科学性原则、系统性原则、经济性原则、定量与定性相结合的原则和通用性与发展性相结合原则这六个原则初步确定一个比较广泛的供应链绩效评价指标体系（表1）。同时，对评价指标代号及指标类型进行了标定。其中，极大型指标是指标值越大越好的指标，又称正向指标；极小型指标是指标值越小越好的指标，又称逆向指标。本研究应用这一指标体系对河北、山东、天津等地区的14条供应链进行调研，调查的实际数据请相关专家进行评分，其评分结果将作为支持向量机评价结果进行训练和检验，同时也作为和只运用支持向量机所得出的训练结果进行比较（表2）［1，2］。
3．1粗集属性约简
把实测数据输入，把这些指标作为条件属性。对于供应链绩效评价结果根据所处情况分为五类（很好，较好、一般、不好、很不好），作为决策属性记为D｛1，2，3，4，5｝，
对决策表进行属性约简，根据粗集理论可以求出哪些是核心属性，哪些是冗余属性，由于属性约简算法比较复杂，采用VB6．0编程进行属性约简。属性约简后的指标体系见表2。此指标体系由于约简了冗余属性，提取了核心属性，为下一步利用支持向量机进行回归识别提供了比较好的基础。
把通过实际调研的数据输入约简后的决策表（表3）。
3．2遗传－支持向量机回归模型的学习
支持向量机学习算法如下：
1）获取学习样本（xi，yi），i＝1，2，……l，其中xi∈Rm，yi∈｛1，－1｝l对样本进行预处理。
2）选择进行非线性变换的核函数及对错分（误差）进行惩罚的惩罚因子C。
3）形成二次优化问题用优化方法。对于此优化问题中参数寻优，通过遗传算法获得，具体步骤如下：①确定遗传算法编码方式。采用十进制整数编码的遗传算法的群体中模式的数目，低阶并且适应度值在群体平均适应度值以上的模式在遗传算法迭代过程中将按指数增长率被采样。②生成初始种群。初始染色体的多少对遗传算法的搜索有影响，对支持向量机算法具有显著影响，为了优化模型往往需要对染色体参数进行适当优化。根据采集数据情况，确定初始种群染色体数目。③计算每个染色体的适应度值f（xi），xi为种群中第i个染色体；④累加所有染色体的适应度值sum＝∑f（xi），同时记录对于每一个染色体的中间累加值S－mid，其中S为总数目；⑤产生一个随机数n，0＜n＜sum；⑥选择其对应的中间累加值S－mid≥n的第一个染色体进入交换集；⑦重复步骤⑤、⑥操作，直到交换集中包含足够多的染色体为止；⑧对于步骤⑦产生的染色体中任意选择两个染色体，染色体进行单点杂交和两点杂交获得一个或多个基因，得到新的两个染色体，来产生新的优良品种；⑨变异运算利用各种偶然因素引起的基因突变，以给定的概率随机地改变遗传基因的值。⑩通过步骤①到步骤⑨获得支持向量机算法的惩罚系数、松弛变量等参数，遗传算法寻优结束。
4）获得αi以及b的值，代入方程中，获得函数拟合的支持向量机。
5）将需预测或分类的数据代入支持向量机方程中获得结果。
本研究中所选评价指标作为供应链评价因素集，供应链绩效评价等级分为5级，目标输出对应以下5类：1、2、3、4、5。
利用表2中的前10数据作为训练样本，对于数据采用以下公式进行归一化处理，以减少各个因子不同量级对于回归效果的影响，并利用matlab软件得出回归结果（图2）。
由图2可以看出拟合效果非常好，从而可以对剩下的4个进行识别，并与采用Bp神经网络对10到14的样本进行评判的结果进行对比（表4）。
通过表4可见，基于粗集的支持向量机识别等级与支持向量机识别的等级除了编号12之外都一样，通过对编号12的数据进行进一步分析可以得出此供应链绩效等级更趋近于一般等级。
4结论
本研究首先利用粗集理论提取出影响供应链绩效评价的核心因素，再使用支持向量机的方法进行模式识别，模式识别过程中，利用遗传算法对相关参数进行寻优操作，取得了良好的效果。由于支持向量机是基于小样本的分类及预测的模型。所以，在本研究实例所给样本极少的情况下做出了较好的预测。由于支持向量机方法是建立在有限样本下进行机器学习的通用方法，因此它在供应链绩效评价和分析中有广泛的应用前景。
参考文献：
［1］王德财．基于支持向量机的供应链绩效评价方法研究［D］．长沙：长沙理工大学，2006．
［2］蔡炜凌．企业供应链项目的综合评价方法研究［D］．河北保定：华北电力大学，2007．
［3］曹庆奎，任向阳，刘琛，等．基于粗集－未确知测度模型的企业技术创新能力评价研究［J］．系统工程理论与实践，2006，9（4）：67－72．
［4］张文修，吴伟志．粗糙集理论与方法［m］．北京：科学出版社，2003．
［5］柯孔林，冯宗宪．基于粗糙集与遗传算法集成的企业短期贷款违约判别［J］．系统工程理论与实践，2008，9（4）：27－34．
［6］BaneRJeem，CHaKRaBoRtYmK．acategoryforroughsets［J］．FoundationsofComputingandDecisionSciences，1993，18（3－4）：167－180．
［7］李顺国，卢新元．基于粗糙集和SVm的工程项目投标风险研究［J］．计算机工程与应用，2008，44（17）：224－227．
［8］苏怀智，温志萍，吴中如．基于SVm理论的大坝安全预警模型研究［J］．应用基础与工程科学学报，2009，17（1）：40－47．
［9］赵洪波，冯夏庭．非线性位移时间序列预测的进化——支持向量机方法及应用［J］．岩土工程学报，2003，25（4）：468－471．
［10］petLeYDn，mantoVaniF，BULmeRmH，etal．theuseofsurfacemonitoringdatafortheinterpretationoflandslidemovementpatterns［J］．Geomorphology，2005，66（1－4）：133－147.
［11］VaLLeJoLe，SHettimam．Creepcrackpropagationandtheprogressivefailureofslopes［a］．in：Deformationandprogressivefailureingeomechanics［C］．London：pergmonpress，1997．
［12］BettenJ．Creepmechanics［m］．2nded．Berlin：Springer，2005．
［13］manDiCDp，GoLZm，KUHa，etal．Signalprocessingtechniquesforknowledgeextractionandinformationfusion［m］．Berlin：Springer，2007．
简述遗传算法的基本原理篇7
关键词：非物质文化遗产；非遗视觉资源；大数据；数字图书馆
中图分类号：G254.9文献标识码：aDoi：10.11968/tsyqb.1003-6938.2016092
abstractVisualresourcesofintangibleculturalheritage，suchastext，images，audioandvideo，and3Dmodelsofdigitizationsystemhavebecomeanimportantcarrierofinformation.Researchondigitalizationtechnologiesofvisualintangibleculturalheritageresourcescontributestothepromotionofintangibleculturalheritageprotection.Basedonananalysisofpresentsituationintheprotectionofintangibleculturalheritage，methodsareputforwardfortheacquisition，organization，understandinganddescriptionofthevisualresourcesofintangibleculturalheritageandvisualsearchandinteractionpatternsareanalyzedfromtheperspectiveofcaseanalysis.
Keywordsintangibleculturalheritage（iCH）；iCHvisualresources；bigdata；digitallibrary
1引言
人类所接受的信息源中超过80%的信息来自于视觉通道（主要包含文本、图像、视频与几何模型等），作为承载视觉通道的信息资源类型称之为视觉资源。随着互联网环境的逐步完善和大数据技术的飞速发展，以文本、图像、音视频和3D模型等为代表的视觉资源逐渐成为数字图书馆最为重要的信息载体，在非物质文化遗产（intangibleCulturalHeritage，iCH，以下简称“非遗”）数字化保护与开发利用体系中也不例外。
非遗作为人类世代相传、与人类生存生活密切相关的文化表现形式、传承方式和文化空间，由于其自身所带的系统性、无形性、复杂性和渐变性等特殊属性[1]，使非遗数字化保护与开发利用难度较大。而非遗视觉资源除了拥有上述自然属性之外，在大数据环境下更是增添了数据量大、非结构化或半结构化、纵深纬度高、语义关联性不强和语义时空性等附属特征，使得非遗视觉资源的高效处理、内容理解和交互反馈就成为需要解决的难点问题，而非遗视觉资源的有效获取、系统组织与结构化描述就成为亟待解决的首要问题。因此，本文从优化非遗视觉资源的获取、组织与描述方式的角度出发，致力于研究大数据环境下非遗视觉资源的获取、组织和描述过程，建立相应的模型，针对知识类和实体类非遗视觉资源提出相应的获取、组织和描述方法。
2非遗视觉资源数字化保护研究现状
国内外关于非遗保护的研究成果非常多，从非遗的社会经济属性分析，到非遗的综合管理，也都出现了许多系统研究的专著。但专门针对非遗数字化保护与开发利用方面的研究并不多，尤其是关于大数据环境下非遗数字化保护、非遗视觉资源开发利用等方面研究更少。
数字化保护与开发利用是非遗保护非常重要的研究领域。自20世纪90年代以来，国际社会和世界各国开始将数字化项目作为发展非遗数字化保护与开发利用的主要策略。如联合国教科文组织推行的“世界的记忆”计划、日本奥兹大学的“狮子舞”数字化保护工程、芝加哥大学与西安大略湖大学的“Sulman木乃伊工程”等。我国非遗数字化保护研究现已进入到飞速发展阶段，各种数字化保护平台、技术与工具层出不穷、琳琅满目[2]。如“中国非物质文化遗产数字博物馆”、“中国非物质文化遗产保护与研究网”[3]、“湖南纸影戏艺术数字化博物馆”、“山西地方戏剧文物文献资源数据库”等[4]。为了解和掌握非遗资源，我国会定期开展全国性非遗普查，采用田野调查、非遗传承人与专家访谈、扫描、拍摄等多种手段相结合的方式，获取了大量极具文化、历史和科研价值，以文本、图像与音视频等视觉资源为主的非遗大数据资源[5]，这一过程使得视觉资源逐渐成为非遗数字化保护体系的主要信息载体[6]，因此，国内外已有相关技术研究主要是围绕非遗视觉资源的获取、组织和描述等方面展开，主要集中在以下三个方面：
（1）非遗视觉资源数字化技术工具的选择与评价研究。如何选择恰当的视觉资源数字化技术、方法对非遗视觉资源进行获取、组织、描述和整理，是非遗数字化保护与开发利用研究必须要解决的关键技术问题。Cheng[7]、余日季[8]等分析了虚拟现实、增强现实等先进技术在非遗数字化保护与开发利用研究中的应用，并提出通过三维重建、恢复与模拟等方式来推进非遗数字化保护、传承与传播；massimiliano等[9]认为3D技术应该在非遗数字化保护领域得到广泛的发展和充分的应用；夏立新等[10]从关联标签的角度对非遗图片资源之间的标签关联关系进行了研究，并采用可视化方法对非遗图片资源的主题特征进行了多元化展示；程秀峰等[11]则对舞蹈类非遗视觉资源的存在形式与类型进行了调研，提出采用社会化网络标签（Sna）形式来揭示非遗视觉资源之间的隐性知识关联。此外，宋丽华[4]、刘勐[12]、林毅红[13]、彭冬梅[14]等均探讨了不同的数字化保护方法、工具在非遗视觉资源数字化保护中的应用，对黎族传统纺染织工艺、甘肃“花儿”艺术、剪纸艺术等非遗数字化保护平台建设进行了研究和评价。
（2）非遗视觉资源数字化保存机制研究。国内外非遗视觉资源收藏机构都在充分利用信息技术来整理、获取、组织、处理和展示其丰富的非遗资源，从而确保了非遗视觉资源数字化长期保存和多元化展示成为其重要的研究主题。从非遗视觉资源数字化保存研究现状来看，当前主要研究重心集中在非遗视觉资源数字化保存的元数据技术和方法方面。如athanasios等[15]就非遗视觉资源数学建模与元数据集成问题进行了研究；noriko等[16]分析了异构非遗视觉资源（如戏曲、舞蹈、建筑、绘画等）在线获取的元数据方法；Regina等[17]对非遗视觉资源元数据格式、标准与技术问题进行了分析。
（3）非遗视觉资源数字化服务研究。随着大数据、云计算、数字影像扫描与传感、三维数字建模、虚拟现实与增强现实、可视化等技术的发展，非遗视觉资源数字化建设项目逐渐具备了多元化、嵌入式、协作化的知识服务与可视化共享功能，尤其是与视觉资源整合、开放式文化教育、自主交互式工具有机结合起来后，极大地推动了非遗视觉资源的数字化服务模式和服务内容。
3大数据环境下非遗视觉资源的获取、组织与描述方法研究
3.1大数据环境下非遗视觉资源数字化保护的新问题
在大数据环境下，海量、异构的非遗视觉资源内容中，包含了对复杂、多元化的客观物理类非遗资源的多角度、全方位的映射与表达，可以让人们体验到更加客观、真实、全面的非遗视觉资源展示与感知，从而为非遗视觉资源数字化保护与服务提供更加有效的支撑，有效推动非遗的全面保护与活态传承，促进非遗客观物理空间与虚拟服务世界的有机融合。这些非遗视觉资源是来源于现实世界中客观事物，彼此之间蕴含着密切的、复杂的时空关联关系，通过对非遗视觉资源的这些时空关联信息的分析、处理和整合，就可以清晰地组织、描述和可视化展示非遗保护、传承与服务的时空变迁。通过对非遗视觉大数据资源的动态挖掘、深度学习和实时分析，使得许多与人类认知相契合的非遗数字化保护与服务的工具、技术和平台也层出不穷，如王蒙等[18]基于主题图理论和方法，以京剧与昆曲为例，建立了非遗信息资源主题图模型；陈路遥等[19]以“歌仔戏”为例，提出了一种基于关键事件技术的非遗信息资源的组织方法与可视化展示技术。
一方面，由于视觉大数据资源因其自身特性，对大数据环境下非遗视觉资源数字化保护的有序化传播、系统化整合、集约化管理、有效组织与描述提出了巨大的挑战。与传统非遗资源相比，非遗视觉大数据资源除了具有时空信息复杂、语义关联多样化、非结构化或半结构化等特点之外，还具有数据规模庞大、动态变化性、无序性、实时性等特征，使得大数据环境下非遗视觉资源的分析和处理具有一定的难度和复杂性。
另一方面，由于非遗视觉资源的来源具有不确定性、异构性和时空关联性，视觉资源本身也不易组织和整合，因此，如何进行视觉资源的高效获取、组织和描述也是大数据环境下非遗视觉资源数字化保护与开发利用的基础性问题。同时，随着非遗规模与类型的逐渐发展和壮大，非遗视觉资源的规模和种类也在不断增长，尤其在“互联网+”时代，三元空间融合下的非遗数字化保护体系在不断产生着无数的非遗视觉资源，只有对其所蕴含的内容进行有效获取与组织、深度理解与结构化描述，才有可能实现对大数据环境下非遗视觉资源的深度分析和有效利用。
因此，大数据环境下非遗数字化保护与开发利用研究，需要从非遗视觉资源的获取、组织、理解和结构化描述等方面进行研究与分析。
3.2非遗视觉资源的获取与组织方法
非遗资源由于其生存环境、分类方法与传承方式的不同，使得非遗视觉资源的类型特征、处理手段、处理技术与保存方法等也会有一定区别，这些差异使其在大数据环境下的存在形式是异构无序、动态变化、时空关联的，且与之相关的视觉资源的生成与也是动态无序的。每一项非遗数字化过程都需要对相关主题信息、繁杂异构信息与隐含关联关系等进行处理。此外，现有非遗视觉资源分析与处理都是基于文本标注的，且以人工标注为主，但传统的人工标注方法在大数据环境下，存在着标注精确性低、时间和人力成本高、分析和处理效率低等问题。因此，如何方便快捷地获取与组织非遗视觉资源，是大数据环境下非遗数字化保护与开发利用的关键问题，而对大规模无关非遗视觉资源的分析、过滤、清洗以及对海量非遗视觉资源的高效组织也是非遗数字化保护与开发利用的核心问题。
在整个非遗视觉资源获取与组织流程（见图1）中，视觉资源过滤是大数据环境下非遗视觉资源获取与分析的关键环节。本文提出了一种基于轮廓特征点的非遗视觉资源整合体系，采用不同的方法从不同层面对获取到的海量非遗视觉资源进行层次过滤、清洗，其中主要的过滤与清洗方法有三种：一是基于显著特征点的非遗视觉资源复杂性过滤，主要用于过滤、清洗掉高度复杂的非遗主体的背景视觉信息。该方法首先检测出非遗视觉对象的显著性区域，通过标识非遗主体的显著性区域，对所有非遗视觉对象进行区域分割，并对区域划分出的高显著区域附近一定阀值区域范围内的所有划分区域数量进行计算，选择其中划分区域数低于设定阀值的区域作为非遗主体的背景区域，并保留下来[20]；二是基于轮廓特征点的非遗视觉资源相似性过滤，主要用于甄选出与特定几何轮廓一致的非遗视觉资源。在经过第一种过滤清洗方法之后，获取到带有简单背景区域的非遗视觉资源，得到符合下一操作要求的过滤清洗效果，在此基础上，对预先设定的分割边界与待识别非遗视觉资源轮廓特征点所构成的几何区域进行一致性检测和评估，并计算得出一致性值，取其中一致性值最高的作为轮廓相似性视觉对象；三是基于内容的非遗视觉资源过滤，主要利用设定的多种标注信息进行非遗视觉资源内容过滤，在前面两轮过滤清洗后获得的非遗视觉资源集合中，将无法提供普适性表象特性的视觉信息过滤清洗掉。如以广西瑶族长鼓为例，经过以上三种过滤方法的反复执行，就能从海量、动态变化、异构无序的“视觉资源海洋”中获取到符合要求的非遗视觉资源。
在现实生活中，并非人人都拥有绘画技能而能手绘出自己希望搜索到的非遗，但几乎人人都能够手绘出自己希望搜索到的非遗轮廓的几何模型（如三角形、圆形、线条等）。简单几何模型是客观物理世界信息化的基础组成元素，现实世界中所有客观物质在转化成视觉效果（如绘画、设计图等）时，都能通过无数简单几何模型有机组合后，展示在人们视觉中，非遗亦不例外。因此，手绘简单几何模型的有机组合是人们展示灵感和构思创意最有效、最自然的手段和方法，并被广泛应用于建筑规划、工业设计、美术等领域。通过简单的手绘几何模型就能够帮助人们将心中正在想、或转载构思的非遗主体转化成具有真实感的粗放型视觉效果，这种粗粒度非遗主体轮廓可成为人们与非遗视觉资源整合平台之间实时交互的一种桥梁。事实上，借助于大数据环境下视觉资源的分析、获取、组织和描述方法而形成的非遗视觉资源数据集，基于粗粒度非遗主体轮廓的视觉搜索模式正逐渐走入人们生活中。
以广西乡村彩调为例（见图3），大数据环境下非遗视觉资源整合平台提供的视觉搜索有两个功能是非常重要的。一是非遗视觉资源的交互与融合搜索。人们只需在非遗视觉资源整合平台中选择所需要检索的非遗类别，并勾画出待检索非遗的大致轮廓，平台就可直接根据待检索非遗主体轮廓，自动对非遗主体轮廓执行轮廓匹配算法，在设定的非遗类别中检索符合要求的非遗视觉资源，并根据非遗主体轮廓在检索区域的相对位置、相对大小和组合关系将轮廓组合在一起。然后，平台根据视觉融合技术将检索出来的视觉资源进行完美融合，形成一幅全新的非遗视觉资源；二是非遗视觉资源的内容搜索。人们在非遗视觉资源整合平台中选择待检索非遗的类别，并勾画出待检索非遗几何轮廓，平台自动对非遗主体轮廓执行轮廓匹配算法，检索得出与该轮廓相似的非遗视觉资源列表。
4.2大数据环境下非遗视觉资源的交互模式
从国内外已有研究来看，传统基于文本标注的视觉搜索模式尽管存在着诸多问题，但仍有不少研究者对其进行研究。而对于视觉资源的深度交互与实时编辑问题却极少有研究者涉及，尤其是对非遗视觉资源的交互编辑问题的研究几乎为零。
伴随着大数据、人工智能与深度计算等信息技术的飞速发展和相关算法的逐步完善，视觉资源的深度交互与实时编辑问题已成为热点课题。非遗的数字化保护与开发利用过程，可采取基于视觉资源融合的方法来实现非遗视觉资源的交互编辑相关功能。具体过程为：给出一个待编辑的非遗视觉资源以及预设定的目标尺寸，在非遗视觉资源知识库中，检索得出一幅设定符合条件的新的非遗视觉资源，将二者有机融合形成一幅更大的视觉资源。这个算法执行的难点在于：一是如何找到符合条件的视觉资源；二是如何保证检索得到的视觉资源与原视觉资源进行有机融合。
本文曾提出基于局部区域特征和非遗主体轮廓结构的视觉描述网络这一方法，借助于该描述方法可实现相应的关联视觉资源的有机融合。首先，设定一个非遗视觉资源为待检索对象，同时，设定其交互编辑的目标尺寸与待融合方法；然后，非遗视觉资源整合平台可根据所提供的视觉搜索功能与相关算法，在非遗视觉资源数据集中检索得到最为合适的视觉资源列表，作为候选内容；接着，对候选资源与待处理非遗视觉资源的轮廓结构、局部特征和主体内容进行一致性、相似性评估，选出待融合的视觉资源；最后，采取局部区域特征融合和边界区域平滑过渡方法，对候选视觉资源进行局部融合和全局变换，使其与待处理非遗视觉资源边界部分进行曲线平滑过渡，并采取视觉融合技术和区域分割方法对二者进行处理[28]。
5结论与展望
在我国文化发展大繁荣的社会背景下，非遗数字化保护事业如何贯彻国民经济与社会发展“十三五”规划纲要、国家“十三五”文化发展规划纲要和国务院办公厅关于加强我国非物质文化遗产保护工作的意见等重大指导性文件精神，在社会公共文化服务体系中获得战略地位和重要作用，成为非遗保护与传承理论、实践研究共同关注的重大问题。非遗数字化作为非遗保护与传承的重要工具和手段，在大数据、视觉搜索与虚拟现实等技术手段的冲击下，势必会给非遗原来赖以生存的原生态空间带来巨大的威胁，导致非遗保护工作受到巨大挑战，但同时也带来了前所未有的机遇。毫无疑问，合理运用大数据、虚拟现实和视觉搜索等现代科技手段进行非遗数字化保护已成为一种必然趋势。
文本、图像、音视频和3D模型等视觉资源逐渐成为非遗数字资源最重要的信息载体，如何高效地分析和利用已有的和即将获取到的非遗视觉大数据资源，将非遗视觉大数据资源转化成知识是当前面临的主要技术瓶颈。尤其是未来十年，在大数据、人工智能和虚拟现实等信息技术的积极推动下，我国非遗视觉资源的数据规模和类型将快速增长，非遗数字化保护研究的深度和广度快速发展，开展大数据环境下非遗视觉资源的获取、组织和描述方法的研究，以为突破这一技术瓶颈提供有效的方法。因此，重视非遗视觉资源分析与利用的研究不仅具有非常重要的理论价值，还具有重要的现实意义。
参考文献：
[1]谈国新，孙传明.信息空间理论下的非物质文化遗产数字化保护与传播[J].西南民族大学学报（人文社会科学版），2013（6）：179-184.
[2]谭必勇，张莹.中外非物质文化遗产数字化保护研究[J].图书与情报，2011（4）：7-11.
[3]宋俊华.关于非物质文化遗产数字化保护的几点思考[J].文化遗产，2015（2）：1-8，157.
[4]宋丽华，李万社，董涛.非物质文化遗产数字化保护与知识整合平台建设[J].图书馆杂志，2015，34（1）：73-81.
[5]黄永林.数字化背景下非物质文化遗产的保护与利用[J].文化遗产，2015（1）：1-10，157.
[6]张旭.非物质文化遗产的数字化展示媒介研究[J].包装工程，2015，36（10）：20-23.
[7]ChengYang，ShouqianSun，CaiqiangXu.RecoveryofCulturalactivityforDigitalSafeguardingofintangibleCulturalHeritage[C].proceedingofthe6thworldCongressonintelligentControlandautomation，2006：10337-10341.
[8]余日季.基于aR技术的非物质文化遗产数字化开发研究[D].武汉：武汉大学，2014.
[9]massimilianopieraccini，GabrieleGuidi，Carloatzeni.3Ddigitizingofculturalheritage[J].JournalofCulturalHeritage，2001，
2（1）：63-70.
[10]夏立新，白阳，孙晶琼.基于关联标签的非遗图片资源主题发现研究[J].图书情报工作，2016，60（2）：22-29.
[11]程秀峰，毕崇武，李成龙.基于Sna的舞蹈类非物质文化遗产隐性知识关联研究[J].图书情报工作，2016，60（2）：30-36.
[12]刘勐，胡文静.甘肃非物质文化遗产传承发展的数字化探索[J].图书馆理论与实践，2013（10）：99-101.
[13]林毅红.基于数字化技术视角下的非物质文化遗产保护研究―以黎族传统纺染织绣工艺为例[J].民族艺术研究，2011（5）：116-121.
[14]彭冬梅.面向剪纸艺术的非物质文化遗产数字化保护技术研究[D].杭州：浙江大学，2008.
[15]athanasiosD.S，ipeki.a.metadatabasedheritagesitesmodelingwithe-learningfunctionality[J].JournalofCulturalHeritage，2009，10（2）：296-312.
[16]norikoK，Juna.CulturalHeritageonline：informationaccessacrossHeterogeneousCulturalHeritageinJapan[C/oL].[2016-01-20].http：//kc.tsukuba.ac.jp/dlkc/e-proceedings/papers/dlkc04pp136.pdf.
[17]ReginaVarnie.-Janssen.文化遗产的数字化与书目存取方法和组织：立陶宛的解决之道[J/oL].[2016-03-08].http：///newtsgj/iflaygt/gjtlzwyyzx/tlzlby/201011/p020101130493555274507.pdf.
[18]王蒙，许鑫.主题图技术在非物质文化遗产信息资源组织中的应用研究――以京剧、昆曲为例[J].图书情报工作，2015，59（14）：15-21.
[19]陈路遥，许鑫.基于关键事件技术的非物质文化遗产形成及演化分析――以两岸同源“歌仔戏”为例[J].图书情报工作，2015，59（14）：22-30.
[20]周莺，张基宏，梁永生，等.基于视觉运动特性的视频时空显著性区域提取方法[J].计算机科学，2015，42（11）：118-121.
[21]欧阳军林，刘建勋，曹步清.基于LBSVm机器学习的相关反馈图像检索[J].计算机工程与应用，2009（2）：112-115.
[22]wangXJ，ZhangL，Lium，etal.arista-imagesearchtoannotationonbillionsofwebphotos[C].proceedingsofieeeConferenceonComputerVisionandpatternRecognition，SanFrancisco，2010：2987-2994.
[23]wangXJ，XuZ，ZhangL，etal.towardsindexingrepresentativeimagesontheweb[C].proceedingsofaCminternationalConferenceonmultimedia，naran，2012：1229-1238.
[24]HuangSS，Shamira，ShenCH，etal.QualitativeorganizationofCollectionsofShapesviaQuartetanalysis[J].aCmtransactionsonGraphics，2013，32（4）：1-10.
[25]段凌宇，黄铁军，alexCK，等.移动视觉搜索技术瓶颈与挑战[J].中国计算机学会通讯，2012，8（12）：8-15.
[26]陈东，王波，席耀一，等.基于邻居向量的近似子图匹配[J].计算机工程与设计，2014，35（11）：4027-4033.
[27]张磊.大规模互联网图像检索与模式挖掘[J].中国科学：信息科学，2013，43（12）：1641-1653.
简述遗传算法的基本原理篇8
关键词：网络入侵数据检测；离散化处理；遗传算法；数据约简
中图分类号：tn711?34；tp393文献标识码：a文章编号：1004?373X（2017）04?0028?04
Researchofpublicnetworkintrusiondetectionmethodbasedonroughsettheory
panGBangyan，ZHanGYanmin
（BasicteachingDepartment，Shangqiuinstituteoftecnology，Shangqiu476000，China）
abstract：traditionalmethodexistshighredundancy，largedimension，pooraccuracyandsoonintheprocessofpublicnetworkintrusiondatadetection.inordertoimprovethereal?timeperformanceandeffectivenessofpublicnetworksecurityprotection，apublicnetworkdetectionmethodbasedontheimprovedroughsettheoryisputforwardtodetectandscreenthedatawhichhasinvasionrisk，optimizethedetectingaccuracybasedonroughsetconcept，andreducetheinformationloss.themDLpoperationalcriterionisadoptedtocompletethediscretizationprocessingofthedata.thegeneticalgorithmisusedtocarryonthedatareduction，derivedataclassificationrulesandidentifytheintrusiondata.thesimulationresultsshowthattheproposedintrusiondatadetectionmethodismoreeffectiveintheaspectsofintrusiondetectionrateanderrorrateincomparisonwiththetraditionalalgorithm.
Keywords：networkintrusiondatadetection；neuralnetwork；geneticalgorithm；datareduction
0引言
近年来信息技术迅猛发展，公共网络已逐渐成为全世界范围内最重要的基础设施之一，对社会各个方面及人类的生产生活方式产生了巨大的影响。网络代表的开放式信息平台是现代信息社会的发展趋势，但网络的开放性同样会带来风险，尤其是和大众联系紧密的公共网络。公共网络攻击行为时有发生，客观上迫切要求建立有效的入侵检测系统。入侵z测技术经过几十年的发展，有一定的进步，但传统方法存在时效性和精简性不足的问题。文献[1]提出入侵检测系统的基础是抽象模型模式匹配，尽管在某些领域内也取得了一些进步，但是随着公共网络的发展和壮大及恶意入侵方式的多样化，这种方法已经不适应目前公共网络的发展趋势要求。本文提出的方法基于优化粗糙集理论对网络入侵原始数据进行处理和分析[2?4]。运用mDLp运算准则完成对入侵数据的离散化处理[5?6]，使用遗传算法对数据进行属性约简，降低维数、去除冗余[7?8]，将导出数据分类规则并对入侵数据进行报警处理，试验证明了本文提出方法能够提高数据的检测率，降低误报警次数，运算简捷同时易于理解[1]。
1基于优化RS入侵检测方法研究
1.1优化粗糙集理论
本文将基于优化粗糙集理论用于实现对公共网络入侵数据的检测。粗糙集理论是一种数学工具，主要描述不完整性和不确定性。可以有效地对各种不完整、不一致、不精确数据信息进行处理，还能够通过分析和推理数据信息，揭示出潜在规律和隐含其中的知识。粗糙集理论最显著的特点是不需要其他任何的先验知识，仅利用数据本身提供的信息可以完成检测。粗糙集理论开辟了一条全新的路径来处理攻击检测样本数据中不易分辨的数据。通常粗糙集方法和模型包括条件属性和决策属性，在不丢失信息前提下对数据进行预处理，应用同样知识进行最小条件属性集约简，保持决策系统相同分类能力的最简形式本文。优化粗糙集相关原理如下：
（1）给定公共网络数据集合X和数据集合Y，其中集合Y是集合X的是等价关系，在X基础对Y进行划分，命名为知识，记为。设定四元组表达系统，U为对象的非空有限集合为论域；R是属性的非空有限集合；V：Va，Va，Va是属性a的值域；f是一个信息函数，aR，xU，f（x，a）Va。
（2）给定基于公共网络数据的关系系统L=（X，Y）是知识库，Y是X上等价关系的一个族集，X为论域；令ZX，Y为X上的一个等价关系。Z的X下近似值：
YZ={H}
Z的Y上近似值：
YZ={HQ≠}
（3）集合eF，如果e独立，ind（e）=ind（F），e为F的一个约简。F中所有必要关系集合记作CoRe（F）。核与约简有如下关系：
CoRe（F）=ReD（n）
（4）设定w=（K，R，V，f）为知识系统，o=pQ，
pQ=，Q是条件属性集，o是决策属性集，p和Q构成决策表。若Q和t是公式，则Qt，Qt。令公式pQ为决策规则，Q和t表达一种因果关系成为规则前、后件。
（5）对粗糙集优化的实现流程是通过修正和调整阈值各项参数，对传统粗糙集理论的近似边界的严格定义进行宽泛化处理。量度不确定是优化粗糙集最大特点，评价一个决策规则是否有效，可以使用两个指标来评价其优劣：覆盖度和准确度。其定义式分别为式（1）和式（2）：
对粗糙集的优化处理能够使其覆盖度和准确度提高。
在上述优化粗糙集原理中，属性知识和数据集合被认为是分类能力。粗糙集理论的主要思想是在保持分类能力不变的前提下利用等价关系来对对象集合进行划分，通过对数据的预处理、离散化、知识约简，得出问题的分类规则和决策。由于粗糙集边界经过优化即宽泛化处理，覆盖度和准确度都有所提高，能够更好地实现对入侵数据检测和识别。
1.2公共网络入侵检测方法研究
基于优化粗糙集的公共网络入侵检测实现流程，如图1所示，主要是根据获取的网络数据连接通过对公共网络数据进行筛选和分析，将进入数据库的原始数据进行离散化处理和遗传数据约简，产生规则集来检测实时的网络数据是攻击数据还是正常连接。
公共网络数据入侵检测流程中对原始数据进行离散化处理和属性约简是最为重要的步骤。包含入侵风险原始数据从公共网络进入数据接收器是不完备和缺失的，由于原始数据的不完备和缺失导致数据信息系统不完备，进入数据库的各种不同的待处理的数据以离散的表现形式存在。运用基于优化的粗糙集方法首先需要对这些原始数据进行预处理然后对数据进行属性约简。对数据的预处理即根据原始数据的数值缺失和不全是离散值的情况特点对数据进行离散化处理。
在对公共网络数据进行入侵检测过程中，mDLD是一种有效的数据信息离散化处理方法，该方法相对独立地按照每个属性的作用，将其持续地获取数据值范围分成合适数量和宽度的子区间，分类嫡设定包含m个类别的数据集U，分布概率分别为数据集U的m个类别分类嫡如下：
（3）
分类嫡是描述上述数据集类别的精度，属性a对S划分后的嫡设属性w将U分为n个子集分类嫡为每个子集U′的嫡加权和比较如式（4）～式（7）所示：
（4）
其中：
（5）
（6）
（7）
从以上数学公式可以推理得出拥有最高信息增益的数据属性是给定集合中具有最高区分度的属性，具有最高增益的离散域值也具有最高的区分度。通过以上的数学方法就完成对粗糙集的数据缺失和非全部离散值的问题进行了离散化处理。
预处理完毕后对数据属性约简是实现入侵数据检测的下一个重要步骤，数据约简可以减少信息的处理量和存储量。基于优化粗糙集的数据约简是通过对属性排序并计算其重要性而实现的。在复杂的数据关系中找出与原始数据具有相同或相似辨别能力的相关属性的最小集合，实现信息约简找出数据库中最简洁、最适用的知识规则。运用遗传算法作全局最优点搜索，识别最优算法参数和初始状态，可以以更短的时间得到更优的属性集约简。
本文采用遗传算法对数据集进行约简，其基本流程把控制序列编码为一个染色体，通过遗传算法来产生控制序列。由于遗传搜索是从决策表的属性核出发，并在整个进化过程中保持不变。选取适应度函数：需要满足条件属性对决策属性依赖度最大和条件属性个数最少这两个条件，才能在属性集是最小约简。对应的函数关系如下：
（8）
式中：a为二进制串长度；CaRD（x）表示体数量；B（x）表示条件属性对决策属性的依赖度。通过对算子的选择、交叉和变异，最终实现稳态繁殖，将属性核加入初始种群，减小了搜索范围，同时交叉和变异不会破坏基因位并可以加快收敛速度，保证入侵数据属性集是最小约简。
通过优化粗糙集对数据进行分辨和规则提取后，数据的准确度和覆盖度都有所提高，证明粗糙集经过优化的有效性，对生成的规则进行过滤和提取，去除置信度低的、冗余的规则。提取规则的流程是从经过处理的决策表中抽取出以规则形式表述的知识，将某些去掉后不影响决策结果生成的规则过滤掉。按照以上的流程和最终提取的规则就完成了对公共网络数据入侵数据的入侵检测，按照形成的规则检测出可疑数据并对入侵报警。
2试验结果与分析
本文通过仿真试验分别对基于优化粗糙集公共网络入侵检测方法和主成分分析（pCa）入侵检测算法进行了效果对比。
通过试验证明本文提出的设计方法有较高的检测率、更加低的误报率，同时训练时间上要比其他算法要低，本文提出的算法具有精确性和有效性。试验数据来自网络入侵检测评判数据库，包含了30余种数据攻击类型如pRoBinG类型，U2R类型，DDoS等类型。将实验数据分成3组，数据的选择如表1所示。
表1试验数据
为了验证本文算法对网络入侵检测性能具有更明显的有效性，试验对pCa算法和基于优化粗糙集公共网络入侵检测方法的有效性进行了充分的数据对比。实验结果如表2～表4所示。
在U2R型数据入侵检测中pCa方法的检测率、误差率和训练时间分别为86.93%，44.81%，0.51s；而基于优化粗糙集的公共网络检测系统在这三个指标的对比中都具有优势，检测率提高到95.28%，误差率大幅度降低到28.23%，时间缩短到0.29s。通过数据对比，本文提出的方法在应对U2R型数据攻击时具有优势。
应对pRoBinG型数据入侵检测中pCa方法的检测率、误差率和训练时间分别为82.26%，40.23%，0.56s。而基于优化粗糙集的公共网络检测系统在这三个指标的对比中都具有优势，检测率也同样具有优势，三个指标分别可以达到93.12%，27.96%和0.21s。
DDoS是一种新型的更具破坏性的攻击方式，是利用更多的傀儡机来发起进攻，以比以前更大的规模来进攻公共网络。从表4的数据来看，在应对新型的数据入侵传统的pCa算法在检测率、误差率和训练时间上显示出的时效性更差。而相反基于优化粗糙集的神经网络算法在以上指标表现时更为有效。
从以上3个表中可以很明显看出，不论是3种数据类型中的哪一种，本文所提出的基于优化粗糙集神经网络入侵检测算法模型的检测率比pCa算法模型在效率和精确度方面有明显的提高，而且模型的误报率以及平均检测时间也要比pCa模型要低，仿真试验表明本文提出基于优化RS入侵检测方法能够在很大程度上提高公共网络的安全入侵检测可靠性，将提出的基于优化RS的公共网络入侵方法用于公共网络入侵行为是一个行之有效的方案。
入侵检测率指标是衡量入侵检测方法是否行之有效的最重要指标，通过仿真试验对本文提出的方法和pCa方法应对常见的攻击方式得出的数据进行统计绘制成检测率综合比较图，如图2所示，本文提出的方法综合检测率在90%以上，在应对常见网络数据攻击行为时具有良好的有效性。
基于粗糙集的公共网络入侵检测系统利用网络工具箱进行测试和训练，实验得到的均方根误差如图3所示。
从实验的仿真结果可以看出，将基于优化粗糙集公共网络入侵方法用于数据入侵检测，较为明显地降低了系统的误报率，提高了各种攻击类型的检测率和目标精度，而且速度较快、收敛容易，有效地改进了公共网络入侵检测系统的性能。
本文的试验分别对基于优化粗糙集公共网络入侵检测方法和主成分分析（pCa）入侵检测算法进行了数据对比可以看出本文提出的设计方法有高检测率、低的误报率，和更短的训练时间。试验证明本文提出的方法更加实用和有效。
3结语
伴随公共网络数据入侵问题的凸显，有效入侵检测成为公共网络安全中一个极为重要的课题。针对传统公共网络入侵检测原始数据精确度低、数据量大、维数多、入侵检测系统误报率、漏报率偏高的现状，在深入研究入粗糙集理论的基础上，本文提出将优化粗糙集理论应用于公共网络入侵检测系统设计。经过大量仿真实验结果证明本文提出的方法是一种高效率、高检测率的网络入侵检测方法，这种优化设计入侵检测系统将会有广泛的应用前景。
参考文献
[1]ZHanGLianhua，ZHanGGuanhua，YULang，etal.intrusiondetectionusingroughsetclassification[J].JournalofZhejiangUniversityScience，2004，5（9）：1076?1086.
[2]Leew，StoLFoSJ，moKK.Datamininginworkflowenvironments：experiencesinintrusiondetection[C]//proceedingsofthe1999ConferenceonKnowledgeDiscoveryandDatamining（KDD99）.aC：Campress，1999：111?120.
[3]王永全.入侵检测系统（iDS）的研究现状和展望[J].通信技术，2008，41（11）：139?143.
[4]weLCHCDJ，LatHRopmSD.aSurveyof802：wirelesssecuritythreatsandsecuritymechanisms[R].westpoint，newYork：Unitedstatesmilitaryacademy，2003.
[5]马海峰，宋进峰，岳新.遗传算法优化的混合神经网络入侵检测系统[J].通信技术，2009，42（9）：106?108.
[6]王文莉，侯丽敏.基于领域粗糙集的入侵检测[J].传感器与微系统，2010，29（6）：36?38.
简述遗传算法的基本原理篇9
摘要自2010年4月股指期货推出后，数量化投资逐渐成为我国资本市场的一个热点。对此，本文以投资者熟知的maCD指标为基础，运用遗传算法和模拟退火算法，建立了一个数量化投资模型。该模型的仿真投资收益明显超出大盘，而风险明显低于大盘。本文基于maCD指标建立数量化投资模型的方法简单、有效，可操作性强，可方便地推广至其他技术指标，在数量化投资领域中可能具有广泛的发展前景。
关键词数量化投资maCD遗传算法模拟退火算法
一、研究背景
与传统投资基于各方面信息和个人判断进行操作不同，数量化投资将适当的金融理论、投资经验等反映在数量模型中，然后利用程序软件代替大脑对海量信息进行科学处理，总结归纳市场规律，最终建立可以重复使用的、不依靠个人主观判断的投资策略。
由于数量化投资的操作策略往往经过了严格的验证，具有较强的系统性和规范性，主观随意性较少，风险可测可控，因此随着计算机数据处理能力的迅速提高，数量化投资获得了快速发展，数量化基金的规模亦迅速扩大。据统计，自2003年以来，数量化基金规模的年均增长速度高达15%，而传统型基金规模的增长速度则低于5%。
很显然，科学的数量模型是数量化投资成败的关键。当前，主流的数量模型均考虑了多方面的因素，既包括各种基本面因素，又包括各种技术因素，涉及较为高深的经济学、金融学、技术分析等知识，模型都比较复杂，理解难度较高，甚至令人望而生畏。对此，本文以人们熟知的技术指标为基础，通过引入遗传算法和模拟退火算法对参数进行优化，建立了一种较为简单、有效的数量模型构建方法，希望能为推动我国刚刚起步的数量化投资发展有所帮助。
二、模型框架
由于maCD指标以经平滑后的股票价格为基础，而股票价格包含了绝大部分的基本信息和技术信息，因此本文以maCD指标为基础研究建立相应的数量化投资模型。
（一）maCD公式
maCD是投资者最熟悉的技术指标之一，主要包括ema、DiF和Dea三个指标，涉及一个已知变量（收盘价p）和三个未知参数（和），公式较为简单。
（二）决策准则
虽然maCD指标的运用方式有很多种，既存在对指标值的应用（如比较DiF和Dea的大小），又存在对形态的应用（如底背离、顶背离等）。对此，本文制定的决策准则相当简单，即：
时，做多
时，做空
三、模型参数优化
（一）参数的科学取值是决定maCD指标投资决策价值的一个关键因素
在一般的技术分析参考书和交易软件中，和通常取12、26和9。然而，该取值并不是最优的。
例如，以2005年1月5日至2010年12月31的沪深300指数为例，根据（公式1）和（公式2），做多业务在和取值12、26和9时，可获得的投资收益为230.55%（收益①）；而在和取40、195、130时，可获得的投资收益为651.98%（收益②）。
因此，参数取值是否合理决定了使用maCD指标进行投资决策时投资收益的高低，决定了maCD指标的投资决策价值。
（二）人工智能算法在技术指标参数优化领域中的突出优势
运用maCD指标建立数量化投资模型的关键在于对公式中的三个参数进行优化。然而，虽然参数取值与投资收益间存在确定的函数关系，但该关系并不能用一个表达式予以直接阐述，因此传统的解析方法在此并不适用。而其他传统方法如随机法和穷举法的优化效率不高。在此情况下，可运用人工智能算法有效解决此类优化难题。
遗传算法（Geneticalgorithms）和模拟退火算法（Simulatedannealingalgorithms）是人工智能的重要分支，两者均从一定的初始值开始，按照明确的规则搜索最优解，并不要求目标函数存在明确的表达式，且具有高效、鲁棒性强等特点。由于技术指标参数与投资收益间的关系相当复杂，不存在明确的函数关系式，因此遗传算法和模拟退火算法在技术指标参数优化领域中具有很高的应用价值。
此外，遗传算法和模拟退火算法的基本原理和运算过程虽然较为复杂，但其运用却相当简单，matLaB等数据处理软件均提供了现成的工具箱供用户方便地使用，且即使不掌握参数优化的原理和运算过程，也不会对数量模型的研究产生重大影响，因此运用遗传算法和模拟退火算法对技术指标参数进行优化的可操作性强。
（三）遗传算法和模拟退火算法应用举例
1.matLaB指令
假设投资收益R和参数、间的关系为R=gain(、)，则matLaB的遗传算法指令和模拟退火算法指令分别为：
[x,fval]=ga(@gain,nvars,[],[],[],[],lb,ub,[],options)；
[x,fval]=simulannealbnd(@gain,x0,lb,ub,options)。
其中：
x和fval是程序返回值，分别为参数、的最优化取值及其所对应的投资收益；
gain是目标函数，可根据（公式1）、（公式2）和（公式3）编写；
nvars是待优化的参数个数；
x0是参数、的初始值；
lb是参数的下界；
ub是参数的上界；
options是matLaB指令的设置选项。
简述遗传算法的基本原理篇10
关键词：遗传算法；tSp；自适应；优化
中图分类号：tp183文献标识码：a文章编号：1009-3044(2008)12-20ppp-0c
aenhancedGeneticalgorithmBasedonSelf-adaptationevaluatingFunctionforthetSpproblem
wanGHui
(GuangDongVocationalinstituteofpublicadministrationGD.Guangzhou510053,China)
abstract:thisarticledescribesaenhancedgeneticalgorithmbasedonself-adaptationevaluatingfunctionforthetSpproblem,andthedesignoftheselection,crossoverandmutationoperations.experimentsindicatethatthisalgorithmremainsthediversifyofthegroupsandavoidleadingtolocaloptimization,andmoreeffectivelyfindoutclosetooptimizationvalue.
Keywords:Geneticalgorithms;tSp;self-adaptation;optimization
1引言
生物通过许多代的进化才能更好的繁殖，适应了不断改变的外界环境因素而生存。遗传算法利用生物基础，将特定问题转化成生物的遗传问题，经过长时间的成长，演化，最后收敛到某个解。生物固有的特征携带于双螺旋的Dna上,子代通过父代的Dna的重组获得或继承到父代的优良特性。在基因重组的过程中，有可能产生变异，使物种有了多样性,有更多的发展和选择空间。适者生存，使整体物种向优良进化。利用这种思想，可以解决很多实际问题。比如tSp问题,即货郎担问题:给定几个城市及所有城市之间的距离,必须决定一条路线,使他能访问到每个城市一次，然后返回到起点并且旅行路径最短。
目前求解tSp问题的主要方法有：Hopfield神经网络方法、模拟退火法以及遗传算法[1]，等等。而遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法、具有良好的全局寻优能力，成为解决tSp问题的有效方法之一。但遗传算法解决tSp问题中一个难解决的问题是如何较快地找到最优解并防止早熟收敛问题。当前许多研究者提出了诸多改进方法来提高遗传算法的性能,如单亲进化遗传算法[2]，其原理是利用父代个体所提供的有效边的信息，使用保留最小边的方法进行个体的进化，此法虽然保证了收敛速度但易陷入局部最优，本文提出了一种改进的遗传算法。
2遗传算法
遗传算法(Geneticalgorithms简称Ga)是由美国michigan大学的JohnHolland[3]教授创建的,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作。选择是遗传算法的关键，它体现了自然界中适者生存的思想；交叉体现了自然界中信息杂交的思想；变异模拟了生物进化过程中的偶然基因突变现象，变异算子则保证了算法能搜索到问题解空间的每一点，从而使算法达到全局最优。
3tSp问题描述
货郎担问题（travelingSalesmanproblem,tSp），也称为巡回旅行商问题[4]，是一个具有广泛的应用背景和重要理论价值的组合优化问题，是一个较古老的问题。最早可以追溯到1759年euler提出的骑士旅行问题。1948年，由美国兰德公司推动，tSp问题成为近代组合优化领域的一个典型难题，并已经被证实是np（nondeterministicpolynomialCompleteness）难解问题[5]。tSp问题其数学描述为：给定m个城市，寻找一条闭合路径，使得每个城市刚好经过一次且总的旅行距离最短。即寻找一条闭合路径（设n维向量表示一条路径）：r=(C1,C2,…,Cn)，使得下列目标函数最小：
上式中Ci为城市号，d(i,j)表示城市i与城市j之间的距离[6]。对于m个城市的tSp问题，其可能的路径组合数为(m-1)!/2。这样，tSp最优解的搜索空间将随着城市数m成指数型增长（所谓的“指数爆炸”）。因此，tSp问题虽易于描述，但找出其最优解却是非常困难的。因而寻找出有效的近似求解算法就具有重要的意义。很多实际应用问题，例如连锁店的货物配送路线等，经过简化处理后，均可建模为货郎担问题，因而对货郎担问题求解方法的研究具有重要实际价值。
用遗传算法解tSp问题，一个旅程很自然地表示为n个城市的排列，如果采用二进制编码来处理，将会很困难，因为进行一次交叉、变异操作，有可能使该位串代表的解已经不适合原问题，结果必需采用特殊的方法来修改位串，每进行一次迭代都进行这样的操作，从而使问题变得复杂起来。如果采用整数变量进行编码，则不会存在这样的问题，使处理问题变得更简洁。采用路径表达方式和整数变量编码：向量ν=(i1,i2…,in)代表一个从城市i1到i2……一直到in再回到i1的旅行。如ν=(345712986)。
4算法设计
4.1流程图
本次算法流程图如下：
4.2输入要求
tSpLiB是一个研究tSp问题的常用数据集，本文选取tSpLiB中48城市的数据集att48作为实验数据集。tSpLiB中给出att48的最优路径长为3.3524公里。
4.3初始化
定义各个参数：这里我们求解48个城市的tSp问题，将种群规模设置为300，交叉概率px=0.5，变异概率pm=0.01，最大迭代的代数为10000。
4.4求解过程
4.4.1染色体群体的初始化
需要初始化300个染色体：可以从不同城市开始对染色体进行初始化。
4.4.2评价函数的定义、约束条件
在Ga中，适应度是描述个体性能的主要指标。根据适应度的大小，对个体进行优胜劣汰，又是驱动Ga的动力,在遗传过程中具有重要意义。对于求解有约束优化问题时，一般采用将目标函数做适当处理，建立适合Ga的评价函数。将目标函数转换成评价函数一般应遵循两个原则：一是适应度必须非负；二是优化过程中目标函数的变化方向应与群体进化过程中评价函数变化方向一致。
（1）评价函数：G－全程的总费用（设有n个城市，从第1个到第n个再回到第1个的总费用），其中G为一常量或一个自适应变化的值。
适应值公式可以表示为：F=G-Cost
每一个染色体的评价值可以这样计算：F=G-Cost，其中Cost表示按顺序遍历此染色体中所有城市所需的费用；G可以是常量也可以是一个随着迭代次数而变化的函数，即G=f(g)，g表示第g代。
如果G取值太大，则无法体现每个染色体之间的差别；如果G取值太小，则可能在一轮选择中有太多的染色体被淘汰，失去了群体的多样性，无法产生更好的后代，从而有可能导致计算收敛于局部最大值。
设第g代的所有染色体中的最大费用为maxg(costj)，0
所以我们可以定义：wh06.tif，其中con定义为随着“代”数g而变化的函数，即con(g)=f(g)，其中1≤con(g)≤∞。可见，当con＝1时，wh07.tif，当con＝∞时，G(g)=maxg(costj)。Con(g)=(maXGenS*n)/(maXGenS-g)（g为“代”数），取n＝4。
（2）约束条件：任何一个染色体向量里面的任何两个点都不能相同。
4.4.3选择
（1）采用式选择法：根据每个染色体的评价值决定其被选择的概率，然后选择产生新的染色体群体。选择概率＝个体最佳适应值/群体总适应值，群体总适应值＝个体最佳适应值的累加(个体最佳适应值的计算方法参考4.4.2)；
（2）如果新的群体的最佳染色体比历史最佳染色体差，则用历史最佳染色体替换新群体中的最差染色体。
4.4.4杂交
（1）染色体的选择：根据杂交概率px选择m个用于杂交的染色体。如果m为奇数，则丢弃最后一个被选择到的染色体；
（2）对于第i对(i=1,…,(m-1)/2)被选中的染色体，产生两个2到city_num-1之间的随机数：j和k（jcity_num/2(city_num为城市数目)，即每一次都不要让超过一半的基因参加杂交；
（3）j和k之间的数不变，两个染色体的第1到j-1位进行杂交，第k+1到city_num位进行杂交；
（注：位＝城市）如：
p1=(123456789)
p2=(416872935)
j=2,k=6，那么第1到1位，第7到9位将被杂交。（注：位＝城市）
则杂交后的后代为：（切割点以“|”表示）
o1=(4|23456|935)
o2=(1|16872|789)
（4）其中，o1和o2中都有重复的数（o1：435；o2：187）。为保证新染色体是有效的，必须采用修正算法：
①对o1，从左到右搜索，当找到一个重复数时停止（如第一个：4）；
②对o2，从右到左搜索，当找到一个重复数时停止（如倒数第三个：7）；
③杂交上两步所得的两个数。得到：
o1=(7|23456|935)
o2=(1|16872|489)
④重复1到3直到o1搜索完毕。得到结果如下：
o1=(7|28416|935)
o2=(1|56872|439)
4.4.5变异
（1）变异位的选择：根据变异概率pm按位选择，即对每个染色体中的每一位（城市）产生一个随机数r，如果r
（2）随机选取同一个染色体中的另外一个位（城市）j（1
V=(761452935)
（3）在改染色体中杂交第i和第j个城市得到新的变异后的染色体，如（假设i=2，i=7）：
V=(791452635)。
4.4.6退出条件
当迭代数达到最大迭代“代”数(10000)时退出。
5实验结果及分析
5.1实验结果
进行多次实验，算法找到的最优路径长度大多落在3.4-3.7之间，实验中在进化到9860代时，找到的48城市的最短路径为3.433997。说明继续进化还会得到更好解。
5.2自适应函数G(g)分析：
Ga用适应值作为复制的选择压力，如果群体的适应值变化不大或过大，会引起选择压力不足或波动，导致选代过程过早收敛或发生震荡。在下面图2（横座标是g，纵座标是G）中，我们可以看出迭代到500代函数G(g)的取值随进化代数g的增加的变化趋势：G(g)随着进化代数的增加而减小而且只与进化的代数有关，是自适应的（随着“代”数而自动调节的）；
通过计算过程中记录的适应值和演化代数数据，可以从图2中看出算法的收敛速度。我们可以看出，在算法执行的早期，个体适应值下降的非常快，说明早期杂交算子作用非常明显，后期，算法效率趋于平缓，但仍有少许变化，可以说明设计的变异算子也起到了作用。
6结束语
本文针对tSp问题，提出了一种全新的遗传算法，设计了编码方式、交叉操作、变异操作和适应度函数以及选择方法，实验数据表明：评价函数能够根据进化实际情况自动调整,克服了简单遗传算法存在早收敛及进化后期搜索效率较低的缺点,提高了算法的收敛速度，较好地解决了群体中多样性和收敛速度的矛盾。我们认为遗传算法的编码和遗传操作必须能够充分反映和充分利用遗传信息，实验结果也进一步表明，同时采用不同的方法控制遗传算法的不同参数,遗传算法的适应性将会随着具有动态自适应能力参数数量的增加而增强。
参考文献
[1]Christofidesn．worst-caseanalysis0fanewHeuristicforthetravelingSalesmanproblem[J].technicalReport,2002(2):27-31．
[2]马欣,朱双东,杨斐.旅行商问题(tsp)的一种改进遗传算法[J].计算机仿真,2003(4):36-37．
[3]HollandJH.adaptationinnaturalandartificialsystems.Univofmichiganpress,annarbormich,1975
[4]潘正君,康立山,陈毓屏.演化计算.北京：清华大学出版社/广西科学技术出版社,20o0:149-161．
[5]Garey.m.andJohnson.D.Computersandintractability.w.H.Freeman.SanFrancisco,1979.
[6]陈国良,王熙法.遗传算法及其应用[m].北京：人民邮电出版社,1996．
收稿日期：2008-03-22