（计算机软件与理论专业论文）基于遗传算法的作曲系统研究.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名 站船j导师嫁烈；( ) 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密 后适用本授权书) 学位论文作者签名：张禾、1 签字日期：2 0 0 b 年 月计曰 导师躲姚l导师签字：o y i 1 山东师范大学颂士学位论文 摘要 遗传算法( g e n e t i ca l g o r i t h m s g a s ) 是模拟达尔文的遗传选择和自然淘汰的 生物进化过程的计算模型，是一种新的全局优化搜索算法，具有简单通用、稳定 性强、适于并行处理以及高效、实用等显著特点，在很多领域得到了广泛应用。 遗传算法借鉴生物界自然选择和自然遗传机制，使用群体搜索技术，尤其适用于 处理传统搜索方法难以解决的复杂的和非线性的问题。由于其具有不依赖于问题 模型的特性、全局最优性、随机转移性而非确定性、隐含并行性等特点，因此遗 传算法更适合复杂问题的优化，与其他优化技术相比存在显著的优势，正越来越 激起人们的广泛研究与应用。 遗传算法的这些优势启发人们可将遗传算法应用于乐曲创作上。遗传算法作 曲是利用遗传算法来控制音乐生成的过程。在作曲过程中首先将给定乐曲进行一 定方式的编码，然后采用交叉、变异等算子对乐曲进行进化，用适应度函数来衡量 进化结果，如此不断进行直到找到最终的满意解为止。 在遗传算法的进化过程中，如果用人的评价来代替客观的适应度函数，则将 这种遗传算法称之为交互式遗传算法。交互式遗传算法通常应用于那些适应度函 数难以精确定义的领域，如音乐、绘画等艺术领域，这些领域需要用到人大量的 主观评价。 同其他方法比较，交互式遗传算法应用于音乐创作时所产生的乐曲更适合人 的欣赏习惯，同时也能够克服普通遗传算法作曲带来的盲目性和随机性的弊端。 所以这种方法被许多人应用于乐曲创作中。 本文论述了遗传算法作曲的基本原理和方法，分析了各种遗传算法作啦系统 的特点，提出了一种新的交互式遗传算法作曲系统。按照这种系统进化后得到的 乐曲能够符合实际的需要。论文的研究内容如下： 1 ) 论文分析了遗传算法作曲的基本原理并介绍了遗传算法作曲的步骤。 2 ) 论文对遗传算法中要用到的音乐知识进行了介绍。 3 ) 论文对遗传算法作曲中的知识表示进行了研究。 4 ) 对遗传算法作曲的适应度函数进行了研究。 5 ) 对各种遗传算法作曲系统的特征及优缺点进行了探讨。 论文的主要贡献在于： 山东师范大学硕士学位论文 1 ) 本文在把遗传算法应用于作曲时提出了一种新的音乐知识的表示方法。 2 ) 本文提出了一种改进的交互式作曲系统，这种作曲系统在作者所定义的进 化操作完成后生成的乐曲比较符合人们的欣赏水平。 最后，文中指出为了进一步完善遗传算法作曲系统需要做的工作，为自己以 后的研究明确了方向。 ， 本文所提出的遗传算法作曲系统对现存的作曲系统在某方面进行了改进，新 的遗传算法作曲系统能对目前遗传算法作曲系统的研究有一定的启发作用。 关键字：遗传算法，适应度函数，遗传算法作曲系统，g a s ，i g a 中图分类号：t p 3 9 1 7 2 2 山东师范大学硕士学位论文 a b s t r a c t g e n e t i ca l g o r i t h m s ，a sac o m p u t a t i o n a lm o d e ls i m u l a t i n gt h eb i o l o g i c a l e v o l u t i o np r o c e s so ft h eg e n e t i cs e l e c t i o nt h e o r yo fd a r w i n 、i saw h 0 1 e n e wg l o b a lo p t i m i z a t i o na l g o r i t h ma n di sw i d e l yu s e di nm a n yf i e l d sw i t h i t sr e m a r k a b l ec h a r a e t e r i s t i co f s i m p l i c i t y ，c o m m o n a b i l i t y ，s t a b i l i t y ， s u i t a b i l i t yf o rp a r a l l e lp r o c e s s i n g ，h i g h e f f i c i e n c y ，a n dp r a c t i b i l i t y g e n e t i ca i g o r i t h m s ，b a s e do nt h eb i o l o g i c a lm e e h a n i s mo fn a t u r a ls e l e c t i o n h e r e d i t ya n dl e v e r a g i n gc o l o n ys e a r c h i n gt e c h n o l o g y ，i sp a r t i c u l a r l y a p p l i c a b l e f o rt h er e s o l u t i o no f c o m p l i c a t e d n o n 一1 i n e a rp r o b l e m s i n t r a c t a b l ew i t h t r a d i t i o n a s e a r c h i n g m e t h o d s a n db e c a u s eo fi t s i n d e p e n d e n c e ，g l o b a lo p t i m i z a t i o n ，a n di m p l i c i tp a r a l l e l i s mi nc o m p l e x p r o b l e ms o l v i n g ，6 ai sd e v e l o p e da n da p p l i e di nm a n yf i e l d sb ym o r ea n d m o r ep e o p l e t h es u p e r i o r i t i e so fg a s e n l i g h t e dp e o p l et ou s ei t i nm u s i c c o m p o s i n g g a sc o m p o s i n gi st h ep r o c e s so fc o n t r o l i i n gt h ec r e a t i n go fm u s i c w i t hg a s i nt h ep r o c e s so fc o m p o s i n g ，f i r s t l y ，w es h o u l de n c o d et h eg i v e n m u s i c ，t h e n ，w ec a ne v o l y et h em u s i cw i t hc r o s s o v e ro p e r a t o ra n dm u t a t i o n o p e r a t o ru n t i lw ef i n dt h es a t i s f y i n gr e s u l t sw h i c ha r es c a e dw i t hf i t n e s s f u n c t i o n i n t e r a c t i v eg e n e t i ca l g o r i t h mi sp r o l a o s e d ，i nw h i c hh u m a ne v a l u a t i o n i su s e di n s t e a do fo b j e c t i v ef i t n e s sf u n c t i o n si nt h ep r o c e s so fg e n e t i c a l g o r i t h m t h ei n t e r a c t i r eg ai so f t e na p p l i e dt ot h ef i e l d si nw h i c ha n a p p r o p r i a t eo b j e c t i v e f i t n e s sf u n c t i o ni sd i f f i c u l tt od e f i n e ，f o re x a m p l e ，t h ea r t i s t i c f i e l dt h a tm a k e sm u c ho fh u m a ns u b j e c t i v ee v a l u a t i o nt o w a r dm u s i co r p a i n t i n g w h e ni n t e r a c t i v eg e n e t i ca l g o r i t h mi su s e di nc o m p o s i n g ，t h ep r o d u c e d m u s i cf u t h e ra d a p t st ot h ea p p r e c i a t i o nc u s t o mo ft h ep e o p l e ，a tt h es a m e t i m e ，i tc a na l s oo v e r c o m et h eb l i n d n e s sa n dt h er a n d o m i c i t yw h i c ha r e c a u s e db yo o h l l l l o nm e t h o d so fg a t h u s m a n yp e o p l ea p p l yt h i sm e a n st o c o m p o s i n g 3 山东师范大学硕士学位论文 t h i st e x td i s c u s s e st h er a t i o n a l e s a n dw a y so f g ac o m p o s i n ga n d a n a l y s e st h ec h a r a c t e r i s t i c so fv a r i o h sk i n do fg ac o m p o s i n gs y s t e m sa n d t h e nd e v i s e san e wi n t e r a c t i v ef i ac o m p o s i n gs y s t e m t h ee v o l v i n gm u s i ci n t h el i g h to ft h i sc o m p o s i n gs y s t e mc a na c c o r dw i t ht h ea c t u a ln e e d t h e r e s e a r c hc o n t e n t so ft h ist h e m sa r ea sf o l l o w s ： 1 ) t h et h e s i sa n a l y s e st h er a t i o n a l e so fg ac o m p o s i n ga n di n t r o d u c e i t ss t e p s 2 ) t h et h e s i si n t r o d u c e sk n o w l e d g ea b o u tm u s i cw h i c hi st ob eu s e di n g ac o m p o s i n g 3 ) t h et h e s i sm a k e sr e s e a r c ho nt h ek n o w e d g er e p r e s e n t a t i o no fg a c o m p o s i n g 4 ) t h et h e s i sm a k e sr e s e a r c ho nt h ef i t n e s sf u n c t i o n so fg ac o m p o s i n g 5 ) t h i st e x td is c u s s e st h ec h a r a n t e r i s t i c s8 n dt h ee x c e l l e n c e sa n dt h e f l a w so fa 1 k i n d so fg ac o m p o s i n gs y s t e m s t h em a j o rc o n t r i b u t i o n so ft h i st h e s i sa r e ： 1 ) t h et h e s i sd e v i s e san e wk i n do fr e p r e s e n t a t i o nm e t h o da b o u tm u s i c k n o w l e d g ew h e ng ai su s e di nc o m p o s i n g 2 ) t h et h e s i sd e v i s e sai m p r o v e di n t e r a c t i v ec o m p o s i n gs y s t e m ，a f t e r t h ee v o l u t i o nw h i c hi sd e f i n e db yt h ea u t h o ri sf i n i s h e d ，t h ep r o d u c e dm u s i c w i t ht h i sk i n do fc o m p o s i n gs y s t e mc a na c c o r dp e o p l e se n j o y i n gh a b i t s f i n a l l y ，ip o i n to u tw o r kw h i c hs h o u l db ed o n ef o rp e r f e c t i n gg a c o m p o s i n gs y s t e m sa n dd e f i n et h ed i r e c t i o r o ft h er e s e a r c hi nt h ef u t u r e f o rm y s e l f t h i sr e x ti m p r o v e st h ec u r r e n ti n t e r a c t i v eg ac o m p o s i n gi ns o m ea s p e c t s ， t h en e wc o m p o s i n gs y s t e mc a ne n l i g h t e nt h er e s e a r c ha b o u tt h ep r e s e n tg a c o m p o s i n gs y s t e m k e y w o r d ： g e n e t i c a l g o r i t h m ， f i t n e s sf u n c t i o n ， g a c o m p o s i n g s y s t e m ，g a s ，i g a 4 山东师范大学硕士学位论文 1 1 引言 第一章绪论 遗传算法( g e n e t i ca 1 9 0 r it h m ，简称g a ) 是基于达尔文生物进化论的自然选 择学说和群体遗传学原理而建立的一种随机全局优化算法。它主要由选择、交叉 和变异三种算子组成，分别模仿达尔文进化过程中的自然选择过程和群体遗传过 程中发生的交配和基因突变等现象。它能在搜索过程中自动获取和积累有关搜索 空间的知识，并自适应地控制搜索过程，从而得到最优解或准最优解。遗传算法 采用简单的编码技术来表示各种复杂的结构，通过对编码表示进行简单的遗传操 作和优胜劣汰的自然选择来指导学习和确定搜索方向。在这一过程中，群体个体 一代一代地得以优化并逐渐逼近最优解。遗传算法( o a ) 作为一种基于自然选择 和遗传变异等生物进化机制的全局概率算法，具有良好的普适性和可规划性，在 形式上简单明了，很方便与其他方法相结合。这些优点启发我们可将遗传算法应 用于乐曲创作上。 遗传算法作曲是利用遗传算法来控制音乐生成的过程。在作曲过程中首先将 给定乐曲进行一定方式的编码，并采用遗传算法中的交叉、变异等算子对乐曲进 行“进化”，用适应度函数来衡量进化结果，如此不断进行直到找到最终的满意解 为止。根据遗传算法作曲中所使用的适应度函数的不同，可将遗传算法作曲系统 分为：交互式系统、基于知识库的系统、基于实例的系统、自发式系统和综合性 系统等。 尽管学者在遗传算法作曲系统的研究上取得了一定的成果，产生的作曲系统 有一定的实用价值，但是许多作曲系统在某方面存在着不足之处，具体表现为：交 互式系统需要人花费大量时间参与对乐曲的评价，这会令参与者感到疲惫不域而 难以承受；对于基于知识库的系统而言 可能多地加进知识库是一项艰巨的工作 提取知识并将生成乐曲的规则或前提尽 基于实例的系统在使用人工神经网络获 得一段乐曲的结构并以获取的知识为基础创作旋律时，容易忽视如短句的构成或 调性等更高层面的音乐特色；在自发式系统中适应度函数完全是由系统本身来定 义，以其作为衡量进化乐曲的标准得出的结果可能与人们平时所欣赏的乐曲差别 很大。 这些不足之处阻碍了遗传算法在作曲中的应用推广，有待于我们对其进行更 进一步的研究。 山东师范大学硕士学位论文 1 2 研究现状 算法作曲的原理是用计算的方法来产生乐旬、旋律及整个片段的过程。到目 i h 为止，已经有许多基于计算机的模拟方法用于乐曲创作。这些方法中有神经网 络方法、专家系统方法以及其他一些从随机事件中获取乐句的方法。这些方法在 作曲过程中通常存在着某种局限性：当使用神经网络方法时，训练中采用的数据 在很大程度上决定着最终的训练效果；而采用专家系统的方法时，要被制定怎样 的规则所限制。与其他的算法相比，遗传算法由于其不依赖于问题参数本身及具 有较好的全局最优解等特性，被越来越多的人应用于乐曲创作中。 遗传算法作曲系统的研究，主要以国外学者的研究成果为基础，国内在这方 面的研究起步较晚。到目前为止，国外学者对遗传算法作曲系统己开展了一系列 的研究工作，建立了一定的理论基础。 h o r n e r 和g o l d b e r g i l 】首次将遗传算法理论应用于音乐。b i l e s 2 1 提出使用交 互式遗传算法( i g a ) 产生爵士乐，并首次提出了交互式遗传算法中的瓶颈问题。 j a c o b 3 】也使用交互式遗传算法产生一种作曲系统；m c i n t ”e 【4 】使用遗传算法根据 一种输入的旋律产生四声部作品。h o r n e r 和a y e r s 5 1 将研究重点集中在如何通过 g a s 使得乐曲能和谐进行。w e r n e r 和t o d d 6 所设计的系统通过采用音符变调概率 表来实现对作曲者和评价函数的共同进化，并以此最终决定乐曲的艺术性。 t h y w i s s e n 7 1 提出了一种用于进化乐曲片段的方法，在此方法中遗传算法的作用是 引导作曲者从搜索空间中找到可能的乐曲。h o r o w i t z i m 设计了一种较为精密的作 曲系统，通过此系统产生出多个不同节奏的乐曲模式。 通过众多学者的努力，遗传算法作曲系统的概念已基本确立。并且根据作曲 过程中所采用原理不同，遗传算法作曲系统也得到了明确的分类。 1 3 本文的主要工作 本文基于遗传算法的基本原理，对将遗传算法如何应用于作曲系统进行了介 绍和分析。具体内容如下： 6 1 对遗传算法这一现代化的优化方法做了较全面的分析介绍。 2 对音乐的基本知识进行了介绍。 3 分析了遗传算法作曲的基本原理，介绍了遗传算法作曲的步骤。 4 介绍了各种遗传算法作曲系统的特征，并对其优缺点进行了探讨。 5 参考目前存在的遗传算法作曲系统，在把遗传算法应用于作曲时提出了一 山东师范大学硕士学位论文 种新的音乐知识的表示方法，并在适应度函数中引进精英策略来提高评价标准 产生了一种改进的作曲系统，并通过实验对作曲系统进行了测试。 7 山东师范大学硕士学位论文 第二章遗传算法的产生、原理及应用 2 1 遗传算法的产生过程 按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历 程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生 存下去就必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争， 以及生物与自然界、无机环境之间的斗争。具有较强生存能力的生物个体容易存 活f 来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产 生后代的机会越来越少，直至消亡。达尔文把这一过程和现象叫做“自然选择， 适者生存”。在短暂的时间里，生物界由最简单的单细胞生物发展到现在的纷繁复 杂、种群繁多的高级生物，充分证明了自然界“自然选择，适者生存”的实际意 义，与之有关的关于生物进化的研究结论，已得到广泛的接受和应用。 自然界的生物进化是一个不断循环的过程，在这一过程中，生物群体不断地 完善和发展。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直 接的借鉴意义【9 j 。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算 机上模拟实现【1 ”，而且还可以模拟进化过程，创立新的优化计算方法，并应用到 复杂的工程领域之中，这就是g a ( g e n e t i ca l g o r i t h m ) 等一类模拟自然进化的计 算方法的思想源泉。 遗传算法研究的历史比较短，其思想可以追溯到2 0 世纪5 0 年代。一般认为， 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 包括三个组成部分：由美国密歇根 大学j o h nh h o l l a n d 教授提出的遗传算法【l “，由美国科学家l a w r e n c ej f o g e l 等人提出的进化规划( e v o l u t i o np r o g r a m m i n g ，e p ) ；由德国科学家i n g o r e c h e n b e r g 和h a m s p a u ls c h w e r f e l 提出的进化策略( e v o l u t i o n a r ys t r a t e g i e s ， e s ) 旧”】这三种方法通称为进化算法( e v o h t i o n a r ya l g o r i t h m s ，e a 或e a s ) 。 随着遗传算法研究和应用的不断深入与扩展，遗传算法和进化计算在2 0 世纪 8 0 年代中期得到了蓬勃发展。1 9 8 5 年，在美国召开了第一届遗传算法的国际会议， 即 c g a ( i n t e r n a t i d n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m ) 。这次会议是遗传 算法发展的重要里程碑，此后每隔一年举行一次。从1 9 9 9 年起，i c g a 和g p ( g e n e t i c p r o g r a m m i n gs o c i e t y ) 的系列会议合并为每年一次的遗传和进化国际会议 ( g e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ，g e c c o ) 。1 9 9 4 年1 月， i e e e 神经网络委员会出版了第一本“进化计算”专集；1 9 9 4 年6 月，i e e e 神经 网络委员会召开了第一届“进化计算”国际学术会议( i e e ei c e c ) 。1 9 9 7 年，该 山东师范大学硬士学位论文 委员会创办了i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 杂志。从1 9 9 9 年开始，i e e ei c e c 与e p 的年会合并为进化计算国际会议( c o n g r e s so n e v o l u t i o n a r yc o m p u t a t i o n ，c e c ) ，每年召开一次。 世界上第一本关于人工智能研究的杂志a it r e n d s 于9 3 年更名为c r i t i c a l t e c h n o l o g yt r e n d s 的启事中讲到“遗传算法、自适应系统、细胞自动机、混沌 理论和人工智能一样，都是对今后十年的计算机技术有重大影响的关键技术。”随 着i n t e r n e t 技术的发展和普及应用，遗传算法的有关研究单位建立了大量的专题 g a 网站，其中最为著名的是由美国海军人工智能音乐研究中心建立的 g a - a r c h i v e s 检索网站( h t t n ：w w w a i c n r l m i l g a l i s t ) ，它包括了世界范 围内的开展遗传算法和进化计算研究的大学和机构，历年来可公开发表的论文和 报告，有关国际会议消息，典型应用案例和程序( 源代码) ，等等。 这些众多的研究单位和频繁的国际学术活动集中反应了遗传算法的学术意义 和研究价值。目前，遗传算法己成为一个多学科、多领域的重要研究方向。 2 2 遗传算法的基本原理 2 2 1 遗传算法的基本思想 g a s 的基本思想是基于d a r w i n 的进化论和m e n d e l 的遗传学说。d a r w i n 的进 化论认为，生物在其延续生存中，都是逐渐地适应于其生存环境。物种的每个个 体的基本特征被后代所继承，但后代又不完全等同于父代。这些新的变化，若适 应环境，则被保留下来。在某一环境中，也是那些更能适应环境的个体特征能被 保留下来，这就是适者生存的原理。m e n d e l 的遗传学说认为，遗传是作为一种指 令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有其特 殊的位置并控制着某种特殊的性质，每个基因产生的个体对环境有一定的适应性， 基因的杂交和基因突变可能产生对环境适应性更强的后代，通过优胜劣汰的自然 选择，适应值高的基因结构就保存下来，而适应值低的则被淘汰。 对于具体的问题，g a s 是将问题的求解表示成“染色体”，再将其置于问题的 “环境”中，根据适者生存的原理，从中选择出适应环境的染色体进行复制，即 再生( r e p r o d u c t i o n ，也称s e l e c t i o n ) ，通过交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 两种基因操作产生出新的一代更适应环境的染色体群。这样一代代不断地进化， 最后收敛到一个最适应环境的个体上，从而求得问题的最优解。图2 1 表达了g a s 的基本步骤。 9 山东师范大学硕士学位论文 2 2 2 遗传算法的基本概念 1 个体和个体空间 所谓个体x 是指一个字符串。所有个体的全体组成的集合称为个体空间，记 为s 。字符串中所采用的不同字符的个数对应于不同的编码。如只采用0 、1 二值 编码，则为二进制；若采用o 、1 、9 这l o 个符号则为十进制编码。 在十进制编码中，若将个体与决策向量对应，则个体空间叩为待优化问题的 可行域。 2 适应度函数i f ( t ) ) 对于一个个体产生的效益称为适应度( 值) ，适应度函数是个体空间到正实数 空间的映射即适应度函数可表示为： f ：s 斗r + 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用 种群中每个个体的适应度值来进行搜索。因此，适应度函数的选取至关重要，直 接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由 目标函数，( x ) 变换而成的。常见的适应度函数有三种，分别为： 直接将待求的目标函数视为适应度函数： 界限构造法，即若目标函数为最小化问题，则 彤) _ 八引饶急 o 山东师范大学硕士学位论文 对极大化问题，有 彤) - 。馄急 其中c 。，c 。i 。为f ( x ) 的最大值、最小值估计，一般可用下面几种方法来选 取：预先指定的一个较大( 小) 的数；进化到当前代为止的最大( 小) 的目标函数值； 当前代或最近几代群体中的最大( 小) 的目标函数值。 进行尺度变换，即对极大化问题，有 足，( 砷卜赢 对极小化问题，有 彤( 砌2 志 c 0 ，c 一厂( x ) 0 f o ，c + f ( x ) 0 其中c 为目标函数界限的保守估计值。 3 遗传算子 最重要的遗传算子有三个，即选择、交叉和变异算子。 选择算子：也称复制算子，是根据个体的优劣程度，决定它在下一代被淘汰 还是被保留。一般来说，通过选择，适应度高的个体在下一代中有较大的生存机 会。常见的选择算子有：赌盘( 比例) 选择、最佳个体保存方法、期望值方法、排 序方法和随机联赛选择。 交叉算子：是指两个相互配对的染色体按某种方式相互交换其部分基因，从 而形成两个新的个体的运算。交叉算子是遗传算法中产生新个体的主要方法。常 见的二进制编码交叉算子有单点交叉、多点交叉、均匀交叉等。十进制编码的交 叉算子有简单交叉和算术交叉。 变异算子：是指将个体染色体编码串中的某些基因位上的基因值用陔基因位 的其他等位基因来替换，从而形成一个新的个体的运算。在二进制编码中，常见 的有基本位变异、均匀变异、高斯变异等；在十进制编码中，有均匀变异和非均 匀变异。 4 控制参数 在g a s 的实际操作中，需适当确定某些参数的值以提高优选的效果，这些参 数主要有： 种群规模m ：即种群中所含个体的个数。m 的大小影响g a s 的有效性。m 太小，g a s 的效果会很差，或根本找不到问题的最优解，因为太小的种群不能提 供足够的采样点。m 太大，会增加计算工作量，使计算时间增大。根据经验，一 山东师范大学硕士学位论文 般m 在3 0 一1 6 0 之间比较合适。 交叉概率p 。：控制着交叉操作的频率。p 。太大，会使适应度大的优良结构遭 到破坏：p 。太小，会使搜索停滞不前。一般p 。取o 2 5 0 7 5 。 变异概率p 。：是决定种群多样性的第二因素。p 。太小，不会产生新的基因 块：p 。太大，会使g a s 成为随机搜索。一般p 。取o 0 1 0 2 。 进化代数t ：算法最大进化的代数，也为算法终止的条件。 目前，以上各参数的取值尚无确定的理论依据，主要通过经验来确定。 2 2 3 遗传算法的基本操作 2 2 3 1 遗传算法的编码 在遗传算法的编码方式的问题上h o l l a n d 建议采用二进制编码，得到了许多 学者的支持。按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标 问题实际表示于遗传算法的染色体位串结构之间建立联系，即确定编码和解码运 算。以下列出了常用的一些编码方法： ( 1 ) 二进制编码 二进制编码是将问题空间的参数表示为基于字符集 o ，1 ) 构成的染色体位串。 1 连续实函数的二进制编码 设一维连续实函数f i x ) ，x u ，v j 采用长度为l 的二进制字符串进行定长编码， 建立位串空间： s 。= f a i ，a 2 ，8 k ，a k = ( a k l ，a k 2 ，a k l ) ，a k l o ，1 k = l 2 一，k ；1 = 1 ，2 ，l ：k = 2 。 其中，个体的向量表示为a k = ( a k l ，a k 2 ，a k l ) ，其字符串形式为s k = a k l a k 2 a k l ( 从右到左依次表示从低位到高位) ，称为个体a k 对应的位串。 对于n 维连续空间函数f i x ) ，x = ( x i ，x 2 ，x 。) ，x u ，v ( i = l 2 ，n ) ，各维变量的 二迸制编码位串的长度为，那么x 的编码从左到右依次构成总长度为l = l 的 拉1 二进制编码位串。相应的g a 编码空间维 s l = a l ，a 2 ，a k ) ，k = 2 。 该空间上的个体位串结构为 a = ( 口叱口1 ，日1 叭口t l2 ，a i22 ，疗2 ，日 2 。，a h 。，口 i ”，a t 2 “，口“”) ，d i ，7 0 ，1 s t = k l 凸1 2 a lk q 口k l2 口22 - 口2 “1 l5 d 2 。- d h 。- a k l ”廿女2 “- 口h ” 2 山东师范大学硕士学位论文 2 组合问题的二进制编码 在很多组合优化问题中，目标函数和约束函数均为离散函数，采用二进制编 码往往具有直接的语义，可以将问题空间的特征与位串的基因相对应比如整数规 划、归纳学习、机器人控制、生产计划等。 ( 2 ) 实数编码 实际使用中可根据需要选择实数位串。实数编码具有精度高，便于大空| 1 白j 搜 索的优点。m i c h a l e w i c z 比较了两种编码的优缺点，指出二进制编码的进化层 次是基因，实数编码的进化层次是个体，用前者理论来指导后者是不合适的。大 量试验结果表明，对同一优化问题，二进制编码和实数编码并不存在显著的性能 差异。 2 2 3 2 遗传算法的适应度函数 遗传算法将问题空间表示成染色体位串空间，为了执行适者生存的原则，必 须对个体位串的适应性进行评价。因此，适应度函数就构成了个体的生存环境。 根据个体的适应值，就可决定它在此环境下的生存能力。一般来说，好的染色体 位串具有比较高的适应度函数值，即可以获得较高的评价，具有较强的生存能力。 由于适应值是群体中个体生存机会选择的唯一确定性指标，所以适应度函数 直接决定着群体的进化行为，为了能够直接将适应度函数与群体中的个体优劣度 量相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越 好。 2 2 3 3 选择算子 选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。在 进行选择操作的之前，首先计算适应度，适应度计算之后是实际的选择，按照适 应度进行父代个体的选择。选择方法通常有如下几种： l 适应值比例选择 适应值比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其 适应值和群体平均适应值的比例有关。通常采用轮盘赌的方式实现。这种方式首 先计算每个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例， 表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者 生存，优胜劣汰”的思想，并且保证优良的基因遗传给下一代个体。 对于给定的规模为”的群体p = a 。，：，口。) ，个体日，的适应值为f ( a ，) ，其 选择概率为 山东师范大学硕士学位论文 加p ：坠，_ ，：1 ，2 ，。 f ( a ，) 浚式决定后代种群中个体的概率分布。经过选择操作生成用于繁殖的交配池 其中父代种群中个体生存的期望数目为 p ( a ) 2 p ( a ，) ， j = 1 , 2 ” 当群体中个体适应值的差异非常大时，最佳个体与最差个体被选择的概率比 也将按指数增长。最佳个体在下一代的生存机会将显著增加，而最差个体的生存 机会将被剥夺。当前群体中的最佳个体将快速充满整个群体，导致群体的多样性 迅速降低，g a 也就过早地丧失了进化能力，这是适应值比例选择容易出现的问 题。 2 排序选择， 排序选择是将群体中个体按其适应值由大到小的顺序排成一个序列，然后将 实现设计好的序列概率分配给每个个体。显然，排序选择与个体的适应值的绝对 值无直接关系，仅仅与个体之间的适应值相对大小有关。排序选择不利用个体适 应值绝对值的信息可以避免群体进化过程的适应值变化过大。由于排序选择概率 比较容易控制，所以在实际计算过程中经常采用，特别是适用于动态调整选择概 率，根据进化效果适时改变群体选择压力。 最常用的排序选择方法是采用线性函数将队列序号映射为期望的选择即线性 排序选择。 排序选挥法的个体选择概率为： p ( x ，) = 土( 矿_ 粤( ，一1 ) l - ，：1 , 2 ，n 其中_ 一为适应函数值最好的个体在选择操作后的期望数量，h 一为适应函数值最差 的个体在选择操作后的期望数量，其他个体的期望数量按等差序列排列。 3 联赛选择 联赛选择的基本思想是从当前群体中随机选择一定数量的个体( 放回或者不 放回) ，将其适应值最大的个体保存到下一代。反复执行该过程，直到下一代个体 数量达到预定的群体规模。联赛规模用q 表示，联赛选择与个体的适应值有间接 关系，注重适应值大小的比较。根据大量的实验总结，联赛规模一般取q = 2 。 4 精英选择 从g a 的整个选择策略来讲，精英选择是群体收敛到优化问题最优解的基本 保障。如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，则将 山东师范大学硕士学位论文 当前群体最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到 下一代，随机替代或替代最差的下一代群体中的相应数量的个体。 2 2 3 4 交叉算子 交叉操作是进化算法中遗传算法具备的原始性的独有特征。g a 交叉算子是 自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个 体，并生成包含更复杂基因结构的新个体。交叉操作一般分为以下几个步骤： 1 从交配池中随机取出要交配的一对个体； 2 根据位串长度l ，对要交配的一对个体随机选择一个或多个的整数k 作为 交叉位置； 3 根据交叉概率p 。( o 0 1 ，2 ，l l ( 9 ，2 ，o ) ( 7 ，4 ，2 l ( 9 ，4 ，1 ) ) f 1 1 ，4 ，2 l ( 14 ，4 ，i x ( 1l ，2 ，2 ) ，( 9 ，2 ，o m 7 ，2 ，1 l ( 9 ，2 ，o ) ) ， ( 1l ，16 ，2 ) 其中，每个小括号里的值表示一个音符的信息。每一大括号里的整数值表示 - d , 节中的音符信息。 6 2 5 交叉与变异的方法 在本系统中，将交叉分为音程交叉、时值交叉和力度交叉三种。每一种类型 的交叉概率均定义为2 0 。 交叉操作如图6 - 3 所示： 交叉和变异 染色体1 染色体2 交叉结果 山东师范大学硕士学位论文 ( 1 ) 音程交叉 ( 2 ) 时值交叉 ( 3 ) 力度交叉 图6 3 染色体交叉图 交叉操作完成之后，对染色体以5 的概率进行变异。其操作定义为改变染色 体的某个组成部分。例如图6 - 4 所示 u 卜i l|j 卜_卜1 变异率：5 图6 4 染色体变异图 6 3 交互式系统的作曲过程 系统的作曲过程如图6 。5 所示。其作曲步骤为：( 1 ) 系统使用者通过试听与要 产生乐曲类型类似的乐曲而进行感知，以增强判断乐曲时的灵敏度。本系统要产 生的乐曲短旬的特点是节奏欢快、活泼的儿歌类型，所以首先选取一定数量的儿 歌进行试听。( 2 ) 系统根据音乐理论首先产生2 0 0 个染色体( 个体) ，考虑到使用者 的负担，从中随机选取2 0 个作为要参与进化的个体。( 3 ) 使用者基于自己的认知 对这些乐曲片段进行逐个评估，并选出最佳乐曲做为评价标准。( 4 ) 系统根据使 4 1 山东师范大学硕士学位论文 用者的评价来对乐曲进行进化操作，随机再从2 0 0 个新的染色体中选择出2 0 个。 过程( 3 ) 和过程( 4 ) 重复进行直到系统使用者找到其所期望的乐瞳。 用户对于乐曲的评价界面如图6 - 6 所示。使用者通过这个交互界面对二十个 乐曲片段进行评估。当用户点击播放按钮时，系统开始演奏乐曲，指示器会显示 乐曲的播放位置。听完之后，用户根据其主观感受对每个乐曲片段进行打分，分 值从3 到+ 3 共七个整数值。其标准参照评价表6 4 。 4 2 图6 - 6 山东师范大学硕士学位论文 评价值一标准一 + 3 一 乐曲非常好听一 十2 p 乐曲比较好听一 + 1 p 乐曲听起来还可芝b 0 p 所有乐曲听起来大体相当一 一l o 参照乐曲听起来还可以一 一2 0 参照乐曲听起来比较好。 一3 0 参照乐曲听起来非常好一 表6 - 4 p 在对2 0 个乐曲片段进行评价完之后，用户选择出他( 她) 所认为的最好的片段， 并使之成为下一代乐曲进化的评判标准。如果没有比原标准更好的，则仍然采用 原来的乐曲做为评价标准。当用户的评价值是正数时，则此染色体以四倍的数量 加入到下代。当所给的评价值是负数或零时，染色体不被选择到下代中。不 足2 0 0 的染色体则随机源交配池中选取。 6 4 交互式系统的作曲实验结果 为了验证系统的有效性，选出了五人用本系统进行了评价实验。这些人根据 自己主观的感知用当前的系统做出欢快的乐曲。每进化一次，都随机从进化结果 中选出一段乐曲评价，经过1 0 次进化后，选出1 0 段乐曲交由这五人对其进行共 同评价，每一片段都要给出分数，分数的范围从+ 1 到+ 1 0 ，评价界面如图