A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


O. Cordón, F. Moya, C. Zarco: A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems. Soft Computing, 6 (5) (2002), pp. 308–319



Relevance feedback techniques have demonstrated to be a powerful means to improve the results obtained when a user submits a query to an information retrieval system as the world wide web search engines. These kinds of techniques modify the user original query taking into account the relevance judgements provided by him on the retrieved documents, making it more similar to those he judged as relevant. This way, the new generated query permits to get new relevant documents thus improving the retrieval process by increasing recall. However, although powerful relevance feedback techniques have been developed for the vector space information retrieval model and some of them have been translated to the classical Boolean model, there is a lack of these tools in more advanced and powerful information retrieval models such as the fuzzy one. In this contribution we introduce a relevance feedback process for extended Boolean (fuzzy) information retrieval systems based on a hybrid evolutionary algorithm combining simulated annealing and genetic programming components. The performance of the proposed technique will be compared with the only previous existing approach to perform this task, Kraft et al.’s method, showing how our proposal outperforms the latter in terms of accuracy and sometimes also in time consumption. Moreover, it will be showed how the adaptation of the retrieval threshold by the relevance feedback mechanism allows the system effectiveness to be increased.

Extended Abstract


author = {O. Cordón, F. Moya, C. Zarco},
title = {A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems},
journal = {Soft Computing},
volume = {6},
number = {5},
pages = {308–319},
year = {2002},
url={http://scimago1.ugr.es/publications/softc-02.pdf http://de.evo-art.org/index.php?title=A_new_evolutionary_algorithm_combining_simulated_annealing_and_genetic_programming_for_relevance_feedback_in_fuzzy_information_retrieval_systems},

Used References

1. Aarts EHL (1989) Simulated annealing and boltzman machines: a stochastic approach to combinatorial optimization and neural computing, Wiley

2. Ba¨ck T (1996) Evolutionary Algorithms in Theory and Practice, Oxford University Press, Oxford

3. Baker JE (1987) Reducing bias and inefficiency in the selection algorithm, Proc. Second International Conference on Genetic Algorithms (ICGA’87), Hillsdale, pp. 14–21

4. Bordogna G, Carrara P, Pasi G (1995) Fuzzy approaches to extend Boolean information retrieval. In: Bosc P, Kacprzyk J (eds), Fuzziness in DatabaseManagement Systems, pp. 231–274

5. Chen H (1998) A machine learning approach to inductive query by examples: an experiment using relevance feedback, ID3, genetic algorithms, and simulated annealing, J Amer Soc Information Sci 49(8): 693–705

6. Cross V (1994) Fuzzy information retrieval, J Intelligent Information Syst 3: 29–56

7. Cordo´n O, Moya F, Zarco C (1999) A brief study on the application of genetic algorithms to information retrieval (in spanish), Proc Fourth International Society for Knowledge Organization (ISKO) Conference (EOCONSID’99), Granada, Spain, pp. 179–186 8. Cordo´n O, Moya F, Zarco C (1999) Learning queries for a fuzzy information retrieval system by means of GA-P techniques, Proc EUSFLAT-ESTYLF Joint Conference, Palma de Mallorca, Spain, pp. 335–338 9. Cordo´n O, Moya F, Zarco C (2000) A GA-P algorithm to automatically formulate extended Boolean queries for a fuzzy information retrieval system, Mathware & Soft Computing 7(2–3) 309–322 10. Dillon M, Desper J (1980) Automatic relevance feedback in Boolean retrieval systems, J Documentation 36: 197–208 11. Dillon M, Ulmschneider J, Desper J (1983) A prevalence formula for automatic relevance feedback in Boolean systems, Information Processing and Management 19(1): 27–36 12. Fan W, Gordon M, Pathak P (2000) Personalization of search engine services for effective retrieval and knowledge management, Proc 2000 International Conference on Information Systems (ICIS) 13. Fan W, Gordon M, Pathak P, Radev D (2001) Automatic term weighting for effective retrieval: a genetic programming approach, submitted to SIGIR 14. Fogel DB (1991) System identification trough simulated evolution. A Machine Learning Approach, Ginn Press, USA 15. Gordon M (1988) Probabilistic and genetic algorithms for document retrieval, Commun ACM 31(10): 1208–1218

16. Gordon M (1991) User-based document clustering by redescribing subject descriptions with a genetic algorithm, J Amer Soc Information Sci 42(5): 311–322

17. Gordon M, Pathak P (1999) Finding information on the world wide web: the retrieval effectiveness of search engines, Information Processing and Management 35(2): 141–180

18. Herrera-Viedma E (2001) Modelling the retrieval process of an information retrieval system using an ordinal fuzzy linguistic approach, J Amer Soc Information Sci 52(6): 460–475

19. Howard L, D’Angelo D (1995) The GA-P: a genetic algorithm and genetic programming hybrid, IEEE Expert 11–15

20. Ide E (1971) New experiments in relevance feedback. In: Salton G (ed.), The SMART Retrieval System, Prentice Hall, pp. 337–354 21. Koza J (1992) Genetic programming. On the Programming of Computers by Means of Natural Selection, The MIT Press

22. Kraft DH, Petry FE, Buckles BP, Sadasivan T (1997) Genetic algorithms for query optimization in information retrieval: relevance feedback. In: Sanchez E, Shibata T, Zadeh LA (eds), Genetic Algorithms and Fuzzy Logic Systems, World Scientific, 155–173.

23. Lo´pez-Pujalte C, Guerrero VP, Moya F (2002) A test of genetic algorithms in relevance feedback, Information Processing & Management. (to appear).

24. Martı´n-Bautista MJ, Vila MA, Larsen HL (1999) A fuzzy genetic algorithm approach to an adaptive information retrieval agent, J Amer Soc Information Sci 50(9): 760–771

25. Michalewicz Z (1996) Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag

26. Mu¨hlenbein H, Schlierkamp-Voosen D (1993) Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization, Evolut Comput 1(1): 25–49

27. Raghavan VV, Agarwal B (1987) Optimal determination of user-oriented clusters: an application for the reproductive plan, Proc Second International Conference on Genetic Algorithms and Their Applications (ICGA’87), Hillsdale, NJ, USA pp. 241–246

28. Robertson AM, Willet P (1994) Generation of equifrequent groups of words using a genetic algorithm, J Documentation 50(3): 213–232

29. Robertson AM, Willet P (1996) An upperbound to the performance of ranked-output searching: optimal weighting of query terms using a genetic algorithm, J Documentation 52(4): 405–420

30. Salton G, McGill MJ (1989) Introduction to Modern Information Retrieval, McGraw-Hill, New York

31. Sanchez E (1989) Importance in knowledge systems, Information Syst 14(6): 455–464

32. Sanchez E, Miyano H, Brachet JP (1995) Optimization of fuzzy queries with genetic algorithms. Application to a data base of patents in biomechanical engineering, Proc Sixth IFSA World Congress, Sao Paulo, Brazil, vol. II, pp. 293–296

33. Sa´nchez L, Couso I, Corrales JA (2001) Combining GP operators with SA search to evolve fuzzy rule based classifiers, Information Sci 136(1–4): 175–191

34. Schwefel H-P (1995) Evolution and optimum seeking. Sixth- Generation Computer Technology Series, John Wiley and Sons

35. Smith MP, Smith M (1997) The use of genetic programming to build Boolean queries for text retrieval through relevance feedback, J Information Sci 23(6): 423–431

36. van Rijsbergen CJ (1979) Information Retrieval (2nd edition), Butterworth, London

37. Vrajitoru D (1998) Crossover improvement for the genetic algorithm in information retrieval, Information Processing and Management 34(4): 405–415

38. Yen JJ, Korfhage RR (1994) Query modification using genetic algorithms in vector spacemodels, Int J Expert Syst 7(2): 165–191 39. Zadeh LA (1965) Fuzzy sets, Information and Control 8: 338– 353


Full Text


internal file

Sonstige Links