Avoiding Premature Convergence of Genetic Algorithm in Informational Retrieval Systems

Abstract

Genetic algorithm is been adopted to implement information retrieval systems by many researchers to retrieve optimal document set based on user query. However, GA is been critiqued by premature convergence due to falling into local optimal solution. This paper proposes a new hybrid crossover technique that speeds up the convergence while preserving high quality of the retrieved documents. The proposed technique is applied to HTML documents and evaluated using precision measure. The results show that this technique is efficient in balancing between fast convergence and high quality outcome

Keywords

• Crossover; genetic algorithm;convergence rate; information retrieval; premature convergence

References

1. J. Jing and M. Lidong, “The Strategy of Improving Convergence of Genetic Algorithm’. TELKOMNIKA, Vol.10, No.8, December 2012, pp. 2063~2068
2. E. S. Nicoară “Mechanisms to Avoid the Premature Convergence of Genetic Algorithms." Petroleum-Gas University of Ploiesti Bulletin, Mathematics-Informatics-Physics Series 61.1 (2009).
3. A. A. Radwan, B. A. Abdel Latef, A. A. Ali, and O. A. Sadeq, ‘Using genetic algorithm to improve information retrieval systems. Proceedings of world academy of science, engineering and technology”, 2006, vol. 17, pp. 6-12.
4. M. H. Marghny and A. F. Ali, “Web mining based on genetic algorithm”. AIML 05 Conference. Cicc, Cairo, Egypt. 2005.
5. B. Klabbankoh and O. Pinngern, “Applied Genetic Algorithms in Information Retrieval”. Retrieved Aug 22, 2009, from http://www.ils.unc.edu/~losee/gene1.pdf
6. S. Kim and B-T. Zhang, “Genetic mining of html structures for effective web-document retrieval”. Applied Intelligence, 2003, vol.18, no.3, pp.243-256.
7. S. A. Kazarlis, S. E. Papadakis, J. B. Theocharis and V. Petridis, “Microgenetic algorithms as generalized hill-climbing operators for GA optimization,” IEEE Trans. Evol. Comput., vol.5, pp.204-217, Jun. 2001.
8. L. Ming, Y. Wang, and Y. M. Cheung, “On convergence rate of a class of genetic algorithms”. In Automation Congress, 2006. WAC'06. World (pp. 1-6). IEEE.

9. S. Kim, B.-T. Zhang, “Web-Document Retrieval by Genetic Learning of Importance Factors for HTML Tags”. In Proceedings of PRICAI Workshop on Text and Web Mining'2000. pp.13~23
10. D. Vrajitoru, “Natural Selection and Mating Constraints with Genetic Algorithms”. To appear in the International Journal of Modeling and Simulation. 2007
11. R. M. Losee, “Learning Syntactic Rules and Tags with Genetic Algorithms for Information Retrieval and Filtering: An Empirical Basis for Grammatical Rules”, Information Processing & Management, 1996, 32(2), pp. 185-197.
12. A. Aly, “Applying genetic algorithm in query improvement problem”. Information Technologies and Knowledge, 2007, vol.1, pp. 309-316.
13. A. Al-Dallal, “The Effect of Hybrid Crossover Technique on Enhancing Recall and Precision in Information Retrieval”, Proceedings of The World Congress on Engineering 2013, Vol. III, WCE 2013, 3 - 5 July, pp1571-1576, London, UK.
14. C. Lopez-Pujalte, V. P. Guerrero-Bote and F. de Moya-Anegon, “Genetic algorithms in relevance feedback: a second test and new contributions”. Information Processing and Management, 2003, vol. 39, pp. 669–687.
15. W. Song, and S. C. Park, “Genetic algorithm for text clustering based on latent semantic indexing”. Computers and Mathematics with Applications, 2009, vol. 57, no.11, pp. 1901-1907.
16. J.-Y. Yeh, J.-Y. Lin, H.-R. Keyword and W.-P. Yang, “Learning to rank for information retrieval using genetic programming”. In Proceedings of ACM SIGIR 2007 Workshop on Learning to Rank for Information Retrieval (LR4IR '07), pp. 41-48. Amsterdam, Netherlands.
17. D. Húsek, V. Snášel, J. Owais, and P. Krömer, “Using genetic algorithms for Boolean queries optimization”. Proceeding of the Ninth IASTED International Conference internet and multimedia systems and applications, 2005, pp. 178-184. Honolulu, Hawaii, USA.
18. D. Vrajitoru, “Large population or many generations for genetic algorithms? Implications in information retrieval”. In F. Crestani, and G. Pasi (Ed.), Soft Computing in Information Retrieval. Techniques and Applications, 2000, pp. 199-222. Physica-Verlag, Heidelberg.
19. G. Desjardins, R. Godin and R. A. Proulx, “Genetic algorithm for text mining”. Proceedings of the 6th international conference on data mining, text mining and their business applications, 2005, vol. 35, pp. 133-142.
20. J. Carroll and T. Lee, “A genetic algorithm for segmentation and information retrieval of SEC regulatory filings”, Proceedings of the 2008 international conference on Digital government research, Publisher: Digital Government Society of North America.
21. P. Simon, and S.S. Sathya, “Genetic algorithm for information retrieval”, International Conference on Intelligent Agent & Multi-Agent Systems. IAMA 2009. pp. 1 – 6, IEEE Conference Publications.
22. H. Drias, I. Khennak, and A. Boukhedra, “A hybrid genetic algorithm for large scale information retrieval”, International Conference on Intelligent Computing and Intelligent Systems, ICIS 2009. IEEE vol: 1, pp. 842 - 846 IEEE Conference Publications
23. P. Pathak, M. Gordon, and W. Fan, “Effective information retrieval using genetic algorithms based matching functions adaption”. 33rd hawaii international conference on science (HICS). Hawaii, USA. 2000.
24. W. M. Spears, and K. A. De Jong, “An analysis of multipoint crossover”, in Foundations of Genetic Algorithms, G. Rawlins, Ed. San Mateo, CA: Morgan Kaufman, 1991, pp. 301–315.
25. D. E. Goldberg, “Genetic algorithms in search, optimization, and machine learning”. Addison-Wesley, 1989.
26. D. Beasley, D. R. Bull, R. R. Martin, “An Overview of Genetic Algorithms: Part 1”, Fundamentals University Computing 15 (2), 58-69, 1993.
27. X. Zhang, K. Wei, and X. Meng, “A XML query results ranking approach based on probabilistic information retrieval model”, 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), 2012, pp.: 915 – 919. IEEE Conference Publications
28. H. M. Pandey, A. Dixitand, and D. Mehrotra “Genetic algorithms: concepts, issues and a case study of grammar induction”, September 2012 , CUBE '12: Proceedings of the CUBE International Information Technology Conference
29. D. Vrajitoru: “Crossover Improvement for the Genetic Algorithm in Information Retrieval”. Information Processing and Management, 1998, 34(4), 405-415.
30. H. Dong, F. K. Hussain, E. and Chang, E. “A survey in traditional information retrieval models”. Second IEEE International conference on digital ecosystems and technologies, 2008, pp. 397 - 402.
31. S.M. Alzahrani and N. Salim, “On the use of fuzzy information retrieval for gauging similarity of Arabic documents”, Applications of Digital Information and Web Technologies, ICADIWT '09. Second International Conference on the Digital Object, 2009, pp.: 539 – 544. IEEE Conference Publications.
32. Manning, C. D., Raghavan, P., and Schütze, H. “An introduction to information retrieval”. Cambridge, England: Cambridge University Press, 2009.
33. A. Al-Dallal, R. S. Abdul-Wahab, “Achieving High Recall and Precision with HTLM Documents: An Innovation Approach in Information Retrieval”, Proceedings of the World Congress on Engineering 2011 Vol. III. pp1883-1888, WCE 2011, 6 - 8 July, 2011, London, U.K.
34. M. Saini, D. Sharma, P. K. Gupta, “Enhancing information retrieval efficiency using semantic-based-combined-similarity-measure”. International Conference on Image Information Processing (ICIIP), 2011, pp. 1 - 4. IEEE Conference Publications.
35. The 4 Universities Data Set. [online]. Available at: http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/ [Accessed 12/11/2009]