ترجمه کامپیوتر اعمال همزمان چندین عملگر جهش در الگوریتم‌های ژنتیک

ترجمه کامپیوتر -27 صفحه

سال 2000

اعمال همزمان چندین عملگر جهش در الگوریتم‌های ژنتیک

چکیده

- عملکرد جهش برای موفقیت‌آمیز بودن الگوریتم‌های جهش، بسیار تعیین‌کننده می‌باشد، زیرا مسیرهای جستجو متنوعی ایجاد کرده و باعث اجتناب از همگرایی به نقاط بهینه محلی  می‌شود. الگوریتم‌های ژنتیک ابتدایی، صرفا از یک عملگر جهش  برای تولید نسل بعدی، استفاده می‌کنند. هر مساله، و حتی هر مرحله از پروسه ژنتیک در یک تک مساله، ممکن است نیازمند عملگرهای جهش متفاوت مناسب، جهت کسب بهترین نتایج باشد. تعیین این که کدام عملگر جهش می‌بایستی به کار گرفته شود، بسیار دشوار بوده و معمولا با تجربه یا سعی و خطا حاصل می‌شود. این مقاله الگوریتم ژنتیکی جدیدی را برای رفع این مشکلات، معرفی می‌نماید؛ الگوریتم ژنتیک جهش پویا . الگوریتم ژنتیک جهش پویا، برای تولید نسل بعدی، همزمان از چند عملگر جهش استفاده می‌کند. نسبت جهش هر عملگر بر حسب بررسی فرزند مربوطه تولید شده از آن، تغییر می‌کند. بنابراین، می‌توان انتظار داشت که عملگرهای جهش مناسب، به گونه‌ای فزاینده به روی پروسه ژنتیک موثر باشند. آزمایشات گزارش شده، بیانگر این مطلب هستند که الگوریتم معرفی شده بهتر از اغلب الگوریتم‌ها با عملگرهای جهش تکی، کار می‌کنند.
کلمات کلیدی: الگوریتم ژنتیک، جهش دینامیک، میزان برازش ، نسل  ، فرزند  ،نسبت جهش

Abstract
The mutation operation is critical to the success of genetic algorithms since it diversifies the search directions and avoids convergence to local optima. The earliest genetic algorithms use only one mutation operator in producing the next generation. Each problem, even each stage of the genetic process in a single problem, may require appropriately different mutation operators for best results. Determining which mutation operators should be used is quite difficult and is usually learned through experience or by trial-and-error. This paper proposes a new genetic algorithm, the dynamic mutation genetic algorithm, to resolve these difficulties. The dynamic mutation genetic algorithm simultaneously uses several mutation operators in producing the next generation. The mutation ratio of each operator changes according to evaluation results from the respective offspring it produces. Thus, the appropriate mutation operators can be expected to have increasingly greater effects on the genetic process. Experiments are reported that show the proposed algorithm performs better than most genetic algorithms with single mutation operators.
keyword:
genetic algorithm -dynamic mutation- fitness value -generation- offspring -mutation ratio

References
    Alba, E., J.F. Aldana, and J.M. Troya. (1993). “Genetic Algorithms as Heuristics for Optimizing ANN Design.” In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms. Innsbruck, Austria, pp. 682–690.
    Booker, L.B., D.E. Goldberg, and J.H. Holland. (1987). “Classifier Systems and Genetic Algorithms.” Technical Report, No. 8, University of Michigan.
    Bramlette, M.F. (1991). “Initialization, Mutation and Selection Methods in Genetic Algorithms for Function Optimization.” In Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 100–107.
    Davis, L. (1989). “Adapting Operator Probabilities in Genetic Algorithms.” In Proceedings of the Third International Conference on Genetic Algorithms, pp. 61–69.
    Davis, L. (1991). Handbook of Genetic Algorithms. Van Nostrand Reinhold.
    Filipic, B. and D. Juricic. (1993). “An Interactive Genetic Algorithm for Controller Parameter Optimization.” In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms, Innsbruck, Austria, pp. 458–462.
    Fogarty, T.C. (1989). “Varying the Probability of Mutation in Genetic Algorithms.” In Proceedings of the Third International Conference on Genetic Algorithms, pp. 104–109.
    Glover, F. (1977). “Heuristics for Integer Programming Using Surrogate Constraints.” Decision Sciences 8, 156–166.Google Scholar
    Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer Academic Publishers.
    Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley.
    Grefenstette, J.J. (1986). “Optimization of Control Parameters for Genetic Algorithms.” IEEE Transactions on Systems, Man and Cybernetics 16(1), 122–128.Google Scholar
    Harp, S.A., T. Samad, and A. Guha. (1989). “Towards the Genetic Synthesis of Neural Networks.” In Proceedings of the Third International Conference on Genetic Algorithms, pp. 360–369.
    Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
    Homaifar, A., S. Guan, and G.E. Liepins, (1993). “A New Approach on the Traveling Salesman Problem by Genetic Algorithms.” In Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 460–466.
    Hong, T.P., and H.S. Wang. (1998). “Automatically adjusting crossover ratios of multiple crossover operators.” Journal of Information Science and Engineering 14(2), 369–390.Google Scholar
    Jong, D. (1975). “An Analysis of the Behavior of a Class of Genetic Adaptive Systems.” Ph.D. Thesis, University of Michigan.
    Karr, C.L. (1991). “Design of an Adaptive Fuzzy Logic Controller Using a Genetic Algorithm.” In Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 450–457.
    Kitano, H. (1990). “Empirical Studies on the Speed of Convergence of Neural Network Training Using Genetic Algorithms.” In Proceedings of the Eighth National Conference on Artificial Intelligence, pp. 789–795.
    Kuncheva, L. (1993). “Genetic Algorithm for Feature Selection for Parallel Classifiers.” Information Processing Letters 46, 163–168.Google Scholar
    Lee, M.A. and H. Takagi. (1993). “Dynamic Control of Genetic Algorithms Using Fuzzy Logic Techniques.” In Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 76–83.
    McCallum, R.A. and K.A. Spackman. (1990). “Using Genetic Algorithms to Learn Disjunctive Rules from Examples.” In Proceedings of the Seventh International Conference on Machine Learning, pp. 149–152.
    Miller, G.F., P.M. Todd, and S.U. Hedge. (1989). “Designing Neural Networks Using Genetic Algorithms.” In Proceedings of the Third International Conference on Genetic Algorithms, pp. 379–384.
    Muhlenbein, H. (1989). “Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization.” In Proceedings of the Third International Conference on Genetic Algorithms.
    Muhlenbein, H., M. Schomisch, and J. Born (1991). “The Parallel Genetic Algorithm as Function Optimizer.” In Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 271–278.
    Munakata, T. and D.J. Hashier. (1993). “A Genetic Algorithm Applied to the Maximum Flow Problem.” In Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 488–493.
    Prinetto, P., M. Rebaudengo, and M.S. Reorda. (1993). “Hybrid Genetic Algorithms for the Traveling Salesman Problem.” In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms. Innsbruck, Austria.
    Robbins, P., A. Soper, and K. Rennolls. (1993). “Use of Genetic Algorithms for Optimal Topology Determination in Back Propagation Neural Networks.” In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms. Innsbruck, Austria, pp. 726–729.
    Schaffer, J.D. (1989). “A Study of Control Parameters Affecting On-line Performance of Genetic Algorithms for Function Optimization.” In Proceedings of the Third International Conference on Genetic Algorithms, pp. 675–682.
    Schiffmann, W., M. Joost, and R. Werner. (1993). “Application of Genetic Algorithms to the Construction of Topologies for Multilayer Perceptrons.” In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms, Innsbruck, Austria, pp. 675–682.
    Schleuter, M.G. (1990). “Genetic Algorithms and Population Structure-A Massively Parallel Algorithm.” Ph.D. Thesis, University of Dortmund.
    Srinivas, M. and L.M. Patnaik. (1994). “Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms,” IEEE Transactions on Systems, Man and Cybernetics 24(4), 656–666.Google Scholar
    Thrift, P. (1991). “Fuzzy Logic Synthesis with Genetic Algorithms.” In Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 509–513.
    Wang, H.S. (1995). “A Study on Dynamic Genetic Algorithms.” Master Thesis, Chung-Hua Polytechnic Institute, Hsinchu, Taiwan.