简述遗传算法的基本原理篇1

摘要自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指令的设置选项。

简述遗传算法的基本原理篇2

关键词：遗传算法；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.

简述遗传算法的基本原理篇3

关键词：遗传算法，混沌，图像分割

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

简述遗传算法的基本原理篇4

关键词：遗传算法；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

简述遗传算法的基本原理篇5

关键词：非物质文化遗产；非遗视觉资源；大数据；数字图书馆

中图分类号：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.

简述遗传算法的基本原理篇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．