基于遗传禁忌算法的案例检索策略研究

基于遗传禁忌算法的案例检索策略研究 黄继鸿，雷战波，李欣苗 (西安交通大学 管理学院，西安 710049) 【摘要】本文将遗传算法和禁忌算法引入案例推理系统。首先使用遗传算法对案例检索中案例属性的权重进行了优化，接着提出了基于遗传禁忌混合算法的检索策略，并且应用于基于案例推理的企业财务危机智能预警支持系统，提高了系统的效率和质量。 关键词: 遗传禁忌算法;案例检索;案例推理;智能预警支持系统 中图分类号: TP18 文献标识码: A Research on case retrieval process based on a hybrid approach using genetic algorithms and tabu search Huang Jihong Lei Zhanbo Li Xinmiao (School of Management, Xi′an Jiaotong University, Xi′an 710049,China) [Abstract] This paper introduces a hybrid approach using genetic algorithms and tabu search into case-based reasoning system. Firstly, GA is used to find an optimal or near optimal weight vector for the attributes of cases in case indexing and retrieving. Then a retrieval process is proposed based on the hybrid approach using GATS, which is applied to intelligent early-warning support system for enterprise financial crisis based on case-based reasoning and improves both accuracy and efficiency of the system. Key words: GATS; Case Retrieval; CBR; Intelligent Early-Warning Support System [1]案例推理CBR(case-based reasoning)是人工是一种有别于以往优化算法的一遗传算法 智能应用中的一种重要推理技术，其推理过程为种新搜索算法，它是建立在自然选择和群体遗传“检索(Retrieve)?重用(Reuse)?修正(Revise)学机理基础上的随机、迭代、进化、并行搜索(寻?存储(Retain)”。而案例检索是CBR的核心技优)算法，模拟自然中的生命进化机制。一般GA术，它直接决定了案例推理的速度和精度，很多包含三个基本算子:?选择;?交叉;?变异。CBR系统实际上就是一个检索系统。在CBR中，通过这三个算子的共同作用对染色体群施加生存检索通常分为两个阶段，即若干相关候选案例的压力，使群体经过一系列迭代得以朝着更好解的检索和最佳案例的选择。目前在AI技术中，案方向进化。同其它传统搜索方法相比，遗传算法例的检索策略主要有最近相邻策略(KNN)、归的主要特点是:GA使用问题参数的编码集，而纳推理策略、知识引导策略等，其中KNN法由不是参数本身进行工作;GA是在点群中而不是于概念清晰、计算简便而被普遍采用。但是，KNN在一个单点上进行寻优;GA仅使用问题本身所在实际应用中存在着两个不可回避的问题:一是具有的目标函数进行工作，而不使用函数的导数案例特征权重的确定;二是其检索时间随案例数或其它的辅助信息;GA使用随机转换规则而不目呈线性增长。这两个问题严重影响着KNN法是确定性规则来工作。 的案例检索质量与效率，尤其对于大型复杂案例尽管GA能够胜任大多数组合优化问题，但库。本文首先使用遗传算法(Genetic Algorithm)是对于像大规模神经元网络的权系数优化，网络对案例属性权重进行了优化，接着提出了基于遗的结构优化等超大规模的优化问题，GA的应用传禁忌混合算法(GATS)的检索策略，并且应就受到了限制。究其原因，主要在于GA在进化用在基于案例推理的企业财务危机智能预警支持搜索过程中，每代总是要维持一个较大的群体规系统(CBR-IEWSS)，提高了系统的检索效率和模，从而使计算次数呈非多项式时间增加，限制质量。 了GA的使用。 GA的另一个不足之处是“早熟”。造成这种1 遗传禁忌算法 未成熟收敛的原因，一方面是GA中最重要的遗1.1 遗传算法及其缺陷 传算子——交叉算子使群体中的染色体具有局部 相似性，从而使搜索停滞不前;另一方面是变异 1 收稿日期: ;修订日期: 基金项目:国家自然科学基金项目(79970012)和国家自然科学基金重大项目(59990470,4) 作者简介:黄继鸿(1978,)，男，博士生。主要从事决策支持系统与人工智能的研究 概率又太小，以至于不能使搜索转向其它的解空的禁忌表中记录着染色体的适应值，渴望水平间进行搜索。此外，GA还有爬山能力差的弱点。 (aspiration level)取父代群体适应值的平均值。 进行TSCO操作时，首先把子代的适应值同渴望1.2 禁忌算法及其缺陷 水平相比较，如果比渴望水平好，则破禁，即这 禁忌(Tabu Search)算法是一种亚启发式个子代染色体进入到下一代之中;如果子代比渴[1](meta-heuristic)随机搜索算法，它从一个初始可望水平差，但不属于禁忌，也接受这个子代;若行解出发，选择一系列的特定搜索方向(移动)作是属于禁忌，则选择最好的那个父代进入到下一为试探，选择实现让特定的目标函数值变化最多代中。从TSCO的重组过程可以看出，具有高适的移动。为了避免陷入局部最优解，TS搜索中采应值的子代进入到下一代的机会是很大的，但是用了一种灵活的“记忆”技术，对已经进行的优并不是所有的高适应值的子代一定都进入到下一化过程进行记录和选择，指导下一步的搜索方向，代。因为TSCO使用了禁忌表，它可以限制适应这就是Tabu表的建立。Tabu表中保存了最近若值相同的子代出现的次数，因此可使群体中尽可干次迭代过程中所实现的移动的反方向移动，凡能保持染色体结构的多样性，从而避免算法早熟。 是处于Tabu表中的移动，在当前迭代过程中是不TSMO的禁忌表定义如下:在每个染色体中允许实现的，这样可以避免算法重新访问在最近增设L个信息位，存储最近L个发生变异的信息若干次迭代过程中已经访问过的解群，从而防止位的号码。每次发生变异时，都将变异信息位的了循环，帮助算法摆脱局部最优解。另外，为了号码与禁忌表中的号码进行比较，若在表中，则尽可能不错过产生最优解的“移动”，TS搜索还属于禁忌范围;若变异后的个体的适应值大于渴采用“释放准则”的策略。 望水平，则可进入下一代。首先，把一个解(染色TS的搜索速度比GA的搜索速度快，但TS体)作为输入(初始解)，经TSMO作用，返回一个对于初始解具有较强的依赖性。一个较好的初始解作为输出。不同之处在于TSMO是一个搜索过解可使TS在解空间中搜索到更好的解，而一个程，因此需要调用适应度函数来确定移动值，并较差的初始解则会降低TS的收敛速度。为此人根据移动值和禁忌表决定接受哪个移动(输出)。们往往使用启发式算法来获得一个较好的初始同样由于TSMO是一个TS搜索过程，在搜索过解，提高TS的性能。TS的另一缺陷是在搜索过程中可以接受劣解，因此TSMO具有强于其它变程中初始解只能有一个，在每代也只是把一个解异算子(例如倒位和部分倒位变异算子)的爬山能移动到另一解，而不像GA那样每代都是对解集力。 (群体)进行操作。 2 基于遗传算法的案例检索权重优化 1.3 遗传禁忌算法 为了克服遗传算法中的早熟问题，并提高它2.1 最近相邻法 的运算效率，许多学者已经做了大量工作，并提最近相邻法是应用最为广泛的方法，用数学 [2,3]出一些改进方法。遗传禁忌算法(GATS)就是其公式表示为: 中一种重要方法，它根据禁忌搜索算法的思想，n Sim,w,Sim (1) 对遗传算法中进化时的核心算子——交叉算子和iji,j,,i1变异算子进行改造。我们引入一个短期记忆装置， 即长度为L的禁忌表，表中记录了最近进行的L这里Sim指案例库中第个旧案例与问题案例的ii个移动。由于这些移动在目前的迭代中是被禁止 的，所以L称为禁忌长度。根据这一原则，我们w综合相似度(也称综合匹配度);指第个属jj重新定义了遗传操作算子，分别记作禁忌交叉算 子(TSCO)和禁忌变异算子(TSMO)。由于禁忌搜iSim性指标的权重;是第个旧案例的第个ji,j索的引入，使之拥有了记忆功能，从而具有较强 的“爬山”能力。它能在搜索过程中跳出局部最属性指标与问题案例的该属性指标的相似度，计优解，转向其它区域进行搜索，从而使获得更好算公式为: 解的概率大大增加。 TSCO算子作为交叉算子，在一个长度为T 2 ,YYjij个案例的相似度;和R分别为对应的属性,Tjk,ikSim (2) ,ij,,Yjln值;为属性的数量，为测试案例的数目。 2.2.2 求解最优权重的算法 ,Y其中是问题案例第个属性指标的值，Y是jji,jStep 1: 随机产生m个特征权重向量 i案例库中第个旧案例第个属性指标的值。 ，组成初始群体; W,(w,w,？w)j12n 选择何种案例推理策略是CBR推理过程中Step 2: 在给定特征权重量下，将测试案例集最为重要的部分，推理策略不同，得到新问题的中的案例分别输入CBR系统进行检索，计算出和解也不同。在CBR-IEWSS中，我们把GATS和测试案例相似度最大的案例; KNN结合起来构成混合检索策略。 Step 3: 根据式(3)计算在给定特征权重向量 下CBR系统的检索精度CR; 2.2 案例属性权重优化 Step 4: 评估m个特征权重向量分别对应的在最近相邻法中案例属性特征权重的确定方系统检索精度(适应度)CR; 法有AHP、Delphi法等，如果案例特征权重不能Step5: 判断GA的收敛条件(如最大进化代正确赋值，KNN检索的案例质量将难以得到保数)是否满足。如果满足，则停止，输出当前适应证，因此首先采用遗传算法来对特征权重进行优度最大的特征权重向量作为最优权重向量;否则，化。 对特征权重向量进行选择、交叉、变异等操作，2.2.1 适应度函数数学模型的建立 产生下一代特征权重向量群体，重复上述过程。适应度函数的建立是GA应用中的关键所在。图1表示了该算法的流程。 对案例特征权重优劣的评价使用测试案例集的检 索精度这个指标，即GA中适应度的度量。GA优随机产生权重 化的目标就是寻找最优特征权重向量从而使检索向量初始群体 精度最好。 将案例分为测试案例集T和参考案例集R， 给定Wi GA适应度函数的数学模型表示为: 测试集T 参考集R n1 CR,CAmax (3) i,n ,1i计算相似度 产生下 一代权 1如果O(T),O(S), ij(i)CA,s.t 重群体 ,i计算系统精度CR i 0否则。, lTR,评价CR ,,ikjkSw (4) min()j,R, (),jik T,ik,1k?选择 N 式中CR为系统检索精度，CA为测试集中第个i?交叉 i判断收敛性 案例的检索精度，取值为1或0。比如，测试集中?变异 Y 第个案例的警度和参考集中最相似案例的警度i 输出最优权重向量 都是“轻警”，则取值为1;否则为0。O(T)是测 i 图 1 最优权重确定的算法流程 O(S)试集中第个案例的预警结果，是参考ij(i) 集中与测试集中第个案例最相似案例的预警结3 基于GATS的混合检索技术在案例推理中i 的应用 S果;是测试集中第个案例和参考集中第jij(i)3.1 编码 3 遗传禁忌算法用于案例的检索，可以采用如于禁忌，那么选择父代中最好的染色体进入到下 表1所示的简单的二进制编码方案，本文以13个财一代。 务指标为例。对于每个基因位，可以用0或1表示。(3)禁忌变异算子(TSMO) 例如资产负债率的基因位是1，表示一个可以接受则TSMO的操作过程如下:设x是一个最优解 的比较合理的债务水平，其值低于k;否则，0代(染色体)，禁忌表的长度为L，用于存放最近发生 表着比较高的债务水平。特别地，数值a,m由专变异的信息位的号码。对x进行变异操作产生新的 家群体根据行业特征和企业的实际情况经过研讨染色体x'，将变异信息位的号码与禁忌表中的号 之后做出决策。各控制参数分别选作:种群容量码进行比较，若在表中，则属于禁忌;若不在表 为50，交叉率P=0.7，变异率P=0.005。 中，且小于渴望水平，则更新禁忌表;否则如果cm 表 1 遗传算法使用时的染色体编码方案 x'的适应值大于渴望水平，则接受它。 财务指标 合理 基因 不合理 基因 4 结束语 1 1 0 营业利润率 ?a 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的基于案例推理的企业财务危3 1 0 资产收益率 ?c 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 定量指标，并且结合专家知识和经5 1 0 净资产收益率 ?e 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 防止危机发生，加强管理，成为企10 1 0 流动比率 ?j k 参考文献: 12 1 0 速动比率 ?l 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 ,1998(9):28,34 近相邻法给出问题的适应度函数，用下列公式计[3] A.H. Mantawy, Youssef L. Abdel-Magid , Shokri Z. Selim. A new genetic-based tabu search algorithm for unit max算: F,1,Sim (5) iicommitment problem [J]. Electric Power Systems Research 3.3 遗传操作 49 (1999) :71–78 (1)选择算子(Selection operator) [4] Hongkyu Jo,Ingoo Han, Bankruptcy prediction using 即从群体中选择优胜的个体，淘汰劣质个体case-based reasoning, neural networks and discriminant 的操作。选择的目的是把优化的个体直接遗传到analysis[J]. Expert Systems with Application, Vol13,No2, 下一代或者通过配对交叉产生新的个体再遗传到pp97-108,1997 下一代。排序选择机制是一种基于群体内各个个[5] 姜丽红,刘豹,案例推理在智能化预测支持系统中的应 体之间的相对适应度设计的等级选择机制，首先用研究[J]. 决策与决策支持系统, 1996,6(4):63-69 根据各个个体的适应度大小进行排序，然后基于[6] Kyung-shik Shin, Ingoo Han. Case-based reasoning 所排序号按某种规则进行选择。我们采用排序选supported by genetic algorithms for corporate bond rating 择机制来进行操作。 [J]. Expert Systems with Applications 16 (1999):85–95 (2)禁忌交叉算子(TSCO) [7] M.T. Elhadi. Bankruptcy support system: taking TSCO具体操作过程如下:设x是父代经过交advantage of information retrieval and case-based 叉产生的一个子代染色体。如果x的适应值大于父reasoning [J]. Expert Systems with Applications 18 代群体适应值的平均值，则接受它进入下一代;(2000) 215–219 否则，如果x不在禁忌表中，同样接受x，如果属 4 5