求解复杂约束问题的基因表达式编程文法模型

摘要

基因表达式编程GEP是进化计算算法家族的新成员．GEP富有特色的个体编码能很方便地表达和解决一批NP问题．但基本GEP难以表达和求解复杂约束．主要工作包括：（1）提出了GEP的上下文无关文法模型gepGram；（2）从理论上证明了gepGrain的表达能力和含单个非终结符的上下文无关文法相同；（3）给出了gepG：ram文法可描述约束问题的GEP求解算法，算法与基因长度具有线性伸缩性；（4）实验证明了本文提出算法具有较高的效率，当基因长度为10^6时，解码仅需0．4s．