有限字符集编码下的模式定理及其证明

doi:10.3969/j.issn.1001-2400.2012.06.016

Abstract

Abstract:

The core theory of the basic genetic algorithm is the schema theorem and the convergence theory. The traditional schema theorem uses binary representation and gets proved. However, in reality, solving many problems using the genetic algorithm needs to use a limited character set encoding method. In this paper, we give some typical genetic operators first, on the basis of which we prove the schema theorem using limited character set encoding. The result shows that the numbers of schema with a low order, a short defined length and a fitness value greater than the average fitness value grow exponentially.

Key words: genetic algorithm, encoding method, schema theorem

CLC Number:

TP301.6

Renqingdaoerji;WANG Yuping. Schema theorem based on limited character set encoding and its proof[J].J4, 2012, 39(6): 99-103.

References

［1］ Holland J H. Adaptation in Natural and Artificial Systems ［M］. Ann Arbor: University of Michigan Press，1975.
［2］ Goldberg D E, Sastry K. A Practical Schema Theorem for Genetic Algorithm Design and Tuning ［C］//Proc of the Genetic and Evolutionary Computation Conference. San Francisco: Morgan Kaufmann, 2001: 328-335.
［3］唐飞, 滕弘飞, 孙治国. 十进制编码遗传算法的模式定理研究［J］. 小型微型计算机系统, 2000, 21(4): 364-367.
Tang Fei, Teng Hongfei, Sun Zhiguo. Decimal Coded Genetic Algorithm Model Theorem ［J］. Mini Micro Systems, 2000, 21(4): 364-367.
［4］明亮, 王宇平. 基于三进制表示的新模式定理［J］. 控制理论与应用, 2005, 22(2): 266-268.
Ming Liang, Wang Yuping. Schema Theorem Based on Ternary Representation ［J］. Control Theory and Applications, 2005, 22(2): 266-268.
［5］徐淑坦, 孙亮, 孙延风. 关于遗传算法模式定理的进一步探讨［J］. 吉林大学学报, 2009, 27(6): 595-601.
Xu Shutan, Sun Liang, Sun Yanfeng. Further Study on Schema Theory of GA ［J］. Journal of Jilin University, 2009, 27(6): 595-601.
［6］王悦, 唐常杰, 杨宁, 等. 基于基因表达式编程的进化模式定理［J］. 四川大学学报, 2009, 41(2): 167-172.
Wang Yue, Tang Changjie, Yang Ning, et al. The Schema Theorem of Evolution Based on Gene Expression Programming ［J］. Journal of Sichuan University, 2009, 41(2): 167-172.
［7］ Xiao F Y, Li P K. An Exact Schema Theorem for Adaptive Genetic Algorithm and Its Application to Machine Cell Formation ［J］. Expert Systems with Applications, 2011, 38(7): 8538-8552.
［8］朱云飞, 蔡自兴, 袁琦钊, 等. 求解多目标旅行商问题的混合遗传算法［J］. 计算机工程与应用, 2011, 47(7): 52-56.
Zhu Yufei, Cai Zixing, Yuan Qizhao, et al. Hybrid Genetic Algorithm for Multiple-Objective TSP ［J］. Computer Engineering and Applications, 2011, 47(7): 52-56.
［9］ Liu M, Sun Z, Yan J, Kang J S. An Adaptive Annealing Genetic Algorithm for the Job Shop Planning and Scheduling Problem ［J］. Expert Systems with Applications, 2011, 38(8): 9248-9255.
［10］ Engin O, Ceran G, Yilmaz M K. An Efficient Genetic Algorithm for Hybrid Flow Shop Scheduling with Multiprocessor Task Problems ［J］. Applied Soft Computing, 2011, 11(3): 3056-3065.
［11］ Gutierrez C, Magarino I G. Modular Design of a Hybrid Genetic Algorithm for a Flexible Job Shop Scheduling Problem ［J］. Knowledge-Based Systems, 2011, 24(1): 102-112.
［12］巩敦卫, 孙晓燕. 基于模式定理的遗传算法交叉和变异概率上限［J］. 控制与决策, 2004, 19(5): 554-556.
Gong Dunwei, Sun Xiaoyan. Based on the Schema Theorem of Genetic Algorithm Crossover and Mutation Probability Limit ［J］. Control and Decision, 2004, 19(5): 554-556.
［13］杨海军, 李敏强. 进化算法中的模式定理及建筑块［J］. 计算机学报, 2003, 26(11): 1550-1554.
Yang Haijun, Li Minqiang. Evolutionary Computation in Schema Theorem and Building Blocks ［J］. Journal of Computers, 2003, 26(11): 1550-1554.
［14］王凌. 车间调度及其遗传算法［M］. 北京: 清华大学出版社, 2003.
［15］ Giovanni L D, Pezzella F. An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem ［J］. European Journal of Operational Research, 2010, 200(2): 359-408.
［16］ Li Y, Chen Y. A Genetic Algorithm for Job Shop Scheduling ［J］. Journal of Software, 2010, 5(3): 269-274.
［17］ Hansen N, Niederberger A S P, Guzzella L. A Method for Handling Uncertainty in Evolutionary Optimization with an Application to Feedback Control of Combustion ［J］. IEEE Trans on Evolutionary Computation, 2009, 13(1):180-197.

[1]	SUN Qian,ZHANG Jiarui,GAO Ling,WANG Yuxiang,YANG Jianfeng. Health prediction algorithm for edge layer nodes [J]. Journal of Xidian University, 2020, 47(3): 32-39.
[2]	XIE Fan,FENG Lifang. Visible light assisted relay communication system and a power allocation scheme [J]. Journal of Xidian University, 2020, 47(1): 95-103.
[3]	YANG Yajun,CHEN Zhang. Hardware trojan attack methods and security analysis under split manufacturing [J]. Journal of Xidian University, 2019, 46(4): 167-175.
[4]	GUO Pengcheng;WANG Xing;CHENG Siyi;WANG Feng. Non-linear frequency modulated signal decomposition based on the improved chirplet time-frequency atom [J]. Journal of Xidian University, 2018, 45(1): 123-128.
[5]	YUAN Haobo;WU Zhengguo;HOU Jianqiang;DANG Xiaojie. Accurate optimization algorithm for the antenna phase center [J]. Journal of Xidian University, 2017, 44(5): 64-68.
[6]	REN Yanqing;LU Zhiyu;BA Bin;WANG Daming. Fast direct position determination method based on the sharpening function genetic algorithm [J]. Journal of Xidian University, 2017, 44(4): 144-150.
[7]	WANG Xiaoli;WANG Yuping;MENG Kun. Release time aware divisible-load scheduling optimization model [J]. J4, 2016, 43(1): 47-53.
[8]	GONG Changmei;SHAO Xiaopeng;WU Tengfei;DAI Weijia;LIU Jietao;ZHANG Jianqi. Focusing of random scattering light by global optimization amplitude modulation [J]. J4, 2016, 43(1): 99-104.
[9]	WU Kai;SU Tao. Design and application of the allpass fractional delay filter [J]. J4, 2015, 42(4): 8-13.
[10]	GE Lin;JI Xinsheng;JIANG Tao. Situation prediction of network information content security incidents using E-IGA-RBF [J]. J4, 2015, 42(4): 107-113.
[11]	FENG Xueyong;YANG Lin;GONG Shuxi;WANG Jianxiao. Design of a plane-wave generator for base station antenna measurements [J]. J4, 2015, 42(3): 33-37.
[12]	WANG Ershen;ZHANG Shufang;CAI Ming;PANG Tao. GPS receiver autonomous integrity monitoring algorithm using the genetic particle filter [J]. J4, 2015, 42(1): 136-141.
[13]	CHEN Lihua;WANG Shicheng;LIU Zhiguo;SUN Yuan. Low cost geomagnetic matching navigation method [J]. J4, 2013, 40(1): 118-122+188.
[14]	ZHANG Yan;FENG Dazheng;QU Xiaoning. A Hybrid Phase Unwrapping Algorithm Combining Branch-Cut and Surface-Fitting for InSAR [J]. J4, 2012, 39(5): 47-53.
[15]	MIAO Zhuang;CHENG Yongmei;PAN Quan;HOU Jun. Research on the approximation algorithm of the evidential thoeory [J]. J4, 2011, 38(2): 187-193.

Schema theorem based on limited character set encoding and its proof

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0