一种基于交互式遗传算法的图书经费分配群决策模型_遗传算法matlab程序

　　[摘要]提出一种基于交互式遗传算法的大学图书馆藏书建设中图书采购经费分配群决策系统模型，通过人工智能技术把定性决策与定量决策结合起来，解决文献经费分配决策中优化目标非定量化、难以较高效率获得专家群体意见共识的问题。模拟实验反映出该模型能以较高效率达成专家群体意见共识。
　　[关键词]交互式遗传算法　图书采购经费分配　群决策模型
　　[分类号]TP182
　　
　　1　引言
　　
　　建立科学的、适用于大学读者的最佳藏书结构是高校藏书建设的核心内容和基本任务。高校图书馆的服务需求相对变化较小，藏书建设具有一定的稳定性；但同时，由于社会的发展、学科专业的调整，对藏书建设又提出前瞻性和突变性的要求，藏书结构也要因之而变，通过调整各种新购图书的经费比例是实现藏书结构改善的重要手段之一。因此，在经费有限的条件下，确定在一定周期内(一般为一年)各种新购图书的最佳经费比例，是图书采访决策中十分关键的一环。各种新购图书经费的比例决策问题是一种典型的隐性目标非结构化决策问题，为了更好地反映本大学特色和学科发展的需要，一些大学图书馆采用由各学科教授等专家构成藏书建设委员会，通过群决策模式来完成各种新购图书经费比例决策，但新购图书经费比例决策具有优化目标非定量化、求解空间极大(组合爆炸)的特点，决策过程中如何以较高的效率获得群体意见共识就成为一个巨大的挑战。传统方法一般是通过利用判断矩阵的一致性、群体一致性指标、个体一致性指标等方法来实现专家群体的共识，这类方法虽然简单，但在可操作性以及群体共识的最大化方面不理想。因此，结合人工智能技术，探讨高效的新购图书经费比例决策问题优化模型，具有重要的理论和实践价值。
　　
　　
　　
　　
　　2　交互式遗传算法
　　
　　2.1　遗传算法
　　遗传算法(Genetic Algorithm，GA)是由美国的J.Holland教授在1975年提出一类模拟生命进化机制(适者生存，优胜劣汰遗传机制)的搜索和优化方法，它的全局最优和隐含并行性特点适用于求解复杂的优化问题，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
　　基本遗传算法的基本优化流程如图1所示，其核心思想是：首先随机或按照一定的条件产生一个初始种群(若干问题解方案)，然后仅用适应度(由实际问题解的评价函数确定)来评价个体的优劣，并以此作为遗传操作的依据进行一代一代进化(一般来说，适应度越大，其被选择进行遗传操作繁殖后代的概率就越大)
　　2.2　交互式遗传算法
　　从2.1中的介绍可知，在遗传算法中，适应度是指引种群优化的唯一方向标，因此，在利用遗传算法解决实际问题时，确定个体解的适应度的量化评价方法可以说是整个优化过程最重要的一步。随着遗传算法的广泛应用，学者们发现传统的遗传算法只能解决性能指标用明确因数(显式)表示的系统优化问题，因为优化问题只有明确定义的性能指标函数才能计算进化个体的适应值。但是，许多实际系统优化问题，如艺术设计、乐曲创作、知识学习和数据挖掘等的性能指标往往难以用明确的函数表示，即它们属于隐式性能指标优化问题，而传统的遗传算法无法解决这类问题。在这样的应用背景下，日本学者高木英行等在前人研究成果的基础上，系统地提出了交互式遗传算法(interac―tive genetic algorithm，IGA)的理论与方法，并将其推广应用于艺术设计、语音识别、复杂产品设计等领域。交互式遗传算法和传统遗传算法的最大区别在于通过交互式手段以用户对个体评估来替代传统的遗传算法(GA)对适应度值进行自动计算的过程。在IGA中，首先将种群的各个个体以某种可视化形式呈现给用户，用户对这些个体进行评估(通常采用百分制、七分制、二分制等打分方式)，并以此作为遗传操作的依据。因此，它既具有传统进化算法的搜索能力强等优点，还具备与决策者交互的机制，特别适合应用于那些适应度函数难以表达，但用户对个体评估较容易的复杂隐性目标优化问题。
　　
　　3　基于交互式遗传算法的新购图书比例辅助群决策模型
　　
　　3.1　应用IGA优化新购图书经费比例决策的主要步骤
　　遗传算法有一种求解复杂系统优化问题的通用框架，结合新购图书经费比例决策问题的实际，具体步骤如下：
　　3.1.1　确定决策变量及约束条件利用IGA算法进行新购图书经费比例决策时，首先要确定图书的分类，本文按照中图分类法，将图书分为22个大类，每个大类比例值的变化都会组合成不同的新购图书经费比例方案。设每类图书的经费比例为Ui(i=1，2，3，…，22)，则决策变量即为ui，约束条件为∑Ui=1。
　　3.1.2　确定表示可行解的染色体编码方法　一个经费比例方案中的某类图书经费比例对应于遗传算法中的一个基因，一个经费比例方案对应于遗传算法中的一个染色体个体，其编码可以选择二进制编码或浮点数编码。同样的问题常常可以使用不同的编码，不同的编码对编程的方便性和程序运行效率的影响是不同的，由于图书经费比例参数属于连续参数，因此采用直接的实数编码方案比二进制编码更为方便。
　　3.1.3　确定个体适应度的量化评价方法　利用IGA算法进行新购图书经费比例决策时，藏书建设委员会的专家对每一个大类图书在本大学的合适比例都有自己的主观判断，据此对每一个新购图书经费比例方案给出评价值(采用百分制)，系统根据各个委员的打分，求取每一个新购图书经费比例方案的平均得分，即作为该方案的适应度值。
　　3.1.4　确定遗传算法优化迭代停止条件若适应度函数的最大值已知，理论上应以找到适应度达到最大值的个体作为遗传算法迭代终止条件，然而图书经费分配这个具体问题，个体适应度最大值虽然已知(100分)，但当藏书建设委员会的专家较多时，找到这样的个体几乎是不可能的，所以具体实现遗传算法时，采用理想解迭代停止法：预先设定一个低于100分的理想分数，当某一个体的适应度值达到该分数时即终止迭代。同时，设定最大遗传代数和进化停滞判定条件(若迭代到一定代数后，连续若干代群体的最优个体的适应度值不再增大，则判定进化停滞。)，到了最大遗传代数或进化停滞时，即使当前最优个体的适应度值没有达到理想值也终止迭代。
　　3.1.5　设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法遗传算法的进化过程主要包括选择、交叉和变异，交叉和变异算子用于产生新的个体，而选择算子保证了遗传迭代中“适者生存”的群体进化现象，在本模型中体现了专家群体意见求同的意向。下面对本模型中的进化算子进行简单介绍。
　　?选择。选择操作是遗传算法中实现群体优良基因传播的基本方式，选择即从当前群体中选择适应值高的个体以生成繁殖池的过程。遗传算法中最常用 的选择方式是轮盘赌(Roulette Wheel)选择方式，也称比例选择或复制，在该方法中，各个个体被选择的概率和其适应度值成比例。在本模型中，设每次轮盘选择操作时候选群体规模为N，则第i个个体被选择进入繁殖池的概率p.为：
　　
　　显然，个体适应度越大，其被选择的概率越高，反之则越低。某个被选择进入繁殖池后的个体则从候选群体中移除。繁殖池里个体数达到种群规模M时则停止轮盘选择操作。
　　?变异。实数编码遗传算法中常用的变异算子有：均匀变异，边界变异，非均匀变异等。由于新购图书比例决策问题中有严格的条件限制，即各个基因(各种图书经费比例)之和必须等于1，因此，变异操作需要成对进行，即须将每个基因作为一次变异操作对象。具体操作过程是：对繁殖池中的每一个体，依次指定个体编码串中的相邻两个基因为变异点候选；对每一个候选变异点，以预先确定的变异概率进行选择，如选中，则对一个基因增加△U，另一个基因减少△U。
　　?交叉。交叉操作是遗传算法中组合出新的个体的主要操作，在串空间进行有效搜索，同时降低对有效模式的破坏概率。一般来讲，交叉操作在两个个体之间进行，但由于新购图书经费比例决策问题中严格的条件限制，如采用异体交叉，容易产生大量的无意义个体，因此，本模型中设计的交叉为自体交叉，即：对繁殖池中的每一个体，随机指定个体编码串中的两个基因为交叉候选；对每一个候选点，以预先确定的交叉概率进行选择，如选中，则互换两个基因的值。一般来讲，交叉概率比变异概率要大。
　　
　　3.2　基于IGA的新购图书经费比例群决策辅助系统流程图
　　由藏书建设委员会专家群体进行基于IGA模型的新购图书经费比例决策过程如图2所示。
　　Step1：显式当前本馆图书结构，作为藏书建设委员会专家们进行新购图书经费比例决策的参考；
　　Step2：根据以前的图书经费比例案例库或由各个委员提出若干初始方案，作为初始种群；
　　Step3：将所有个体(各个比例方案)显式给各个专家；
　　Step4：各个专家综合各种主、客观准则和自己主观认识给定每一个个体的评价值；
　　Step5：藏书建设委员会主持人判断当前最优方案的平均评价值是否达到理想值，如是，则结束迭代，否则转到Step7；
　　Step6：软件系统根据当前进化代数是否达到规定值或进化是否已停滞，如是，则结束迭代，否则转到Step7；
　　Step7：系统进行遗传操作，包括选择、交叉、变异，然后转到Step3。
　　
　　4　模拟实验
　　
　　针对大学图书馆藏书建设中新购图书经费比例决策这样一个目标难以显式定量表达的非结构化决策问题，基于本文提出的交互式遗传算法群决策系统模型，在VS2005环境下开发了一个原型系统(为了简化开发，原型系统中进化停止条件仅由最大代数确定)，进行了新购图书经费比例决策模拟实验。交叉概率设为O.6，变异概率设为0.15，为了尽量降低应用IGA时人的疲劳问题的影响，最大进化代数和种群规模均设置得较小，种群规模为20，最大迭代次数为20，初始方案群(第O代)由参与模拟实验的某图书馆lO位馆员提出(每人提出2个)。整个实验过程费时约2小时。初始最优方案平均评价分值为69.6分，实验中20次迭代结束时，最优方案平均评价分值达到了82.3分。最优方案进化情况如图3所示。
　　分析进化情况可以看到，在最初10代内，最优个体评价分快速增长，之后总体增长缓慢，甚至出现了评价分振荡的情况，这可能与随着评价次数的增多，馆员的疲劳程度增大有关。因此，在实际应用该模型开发实用系统时，最大进化代数还可适当减少，同时，在遗传操作中增加最优保留策略，应能避免振荡。
　　
　　5　结语
　　
　　目前，已有一些学者进行了将遗传算法应用于图书采购决策问题的研究。文献[6]从尽量满足读者采购需求的角度出发，将每位读者要求订购的书目用一个集合来表示，所有读者的采购要求构成一个集合簇，用遗传算法计算该集合簇的碰集，遗传运算中适应度由采购方案个体与集合簇中的集合相“碰”的多少来确定；文献[7]利用神经网络建立图书的图书内容关键词、图书分类号、图书出版社、图书出版日期、图书版本号、图书价格、图书是否属于重点学科等7种属性(作为输入神经元)与是否被采购(作为输出神经元)之间的非线性映射关系，采用遗传算法对神经网络的权值、阈值等进行优化，遗传运算中适应度由期望输出与实际输出的误差来确定。这种模型中，图书属性与是否被采购的映射关系实际上由训练样本情况来决定的，也就是由已购情况预测(决策)待购情况。上述模型针对的都是具体书目的采购决策，考虑的因素均较单一，且在利用遗传算法时，个体评价函数(适应度函数)都是能用定量数学式显式表达的，本质上均是传统遗传算法的应用。而大学图书馆藏书建设中新购图书经费比例决策问题需要考虑的影响因素众多，如学校类型、专业特色、人才培养定位、现有馆藏情况、读者层次分布等，这类决策本质上是一种典型的非结构化决策，要建立有效综合各种影响因素的定量数学评价模型是及其困难的。群体决策作为解决非结构化决策问题的重要手段，已越来越引起人们的重视，本文尝试将群决策引入图书采购经费分配决策问题求解，并采用交互式遗传算法来解决快速高效达成群体共识这一群决策瓶颈问题。模拟实验反映出该方法能以较高的效率提高最终购书经费比例方案的群体共同认可度。

相关热词搜索：遗传 经费 算法 一种基于交互式遗传算法的图书经费分配群决策模型 图书情报 图书情报硕士