Inteligentne operatory genetyczne w ewolucyjnym podejściu do rozwiązywania problemów planowania

• Autorzy: Maciej Norberciak
• Języki publikacji: PL

Abstrakty

Niniejsza praca opisuje oparty o algorytm ewolucyjny, w pełni automatyczny system rozwiązujący problem układania planu zajęć na uczelni. Za problem testowy wybrano problem układania semestralnego planu zajęć na Wydziale Informatyki i Zarządzania (WIZ) Politechniki Wrocławskiej. Ze względu na znaczny rozmiar problemu oraz mnogość sytuacji wyjątkowych i różnorodnych ograniczeń nie można było w prosty sposób zastosować rozwiązań ogólnych. Problem ten opisano w rozdziale 2. Rozdział 3 opisuje najważniejsze cechy zastosowanego przez autora podejścia do rozwiązania tego problemu, tj. metodę reprezentacji rozwiązania, sposoby inicjalizacji populacji, oceny uzyskanych rozwiązań oraz przyjęte zasady ewolucji. W rozdziale 4 zawarto opis opracowanych operatorów genetycznych oraz badania dotyczące kolejności i miejsca ich stosowania. Ostatni rozdział podsumowuje osiągnięte wyniki i wyznacza perspektywy dla dalszych badań. (fragment tekstu)

Słowa kluczowe

PL

Algorytmy; Rozwiązywanie problemów

EN

Algorithms; Solving problems

• Czasopismo: Prace Naukowe Akademii Ekonomicznej we Wrocławiu
• Rocznik: 2003
• Numer: nr 975 Pozyskiwanie wiedzy i zarządzanie wiedzą
• Strony: 340--350

Twórcy

autor

Maciej Norberciak

• Politechnika Wrocławska

Bibliografia

• Alvarez-Valdes R., Crespo E., Tamarit J.M.: Design and implementation of a course scheduling system using Tabu Search. "European Journal of Operational Research" 137, 2001.
• Burke E.K., Elliman D.G., Weare R.F.: A University Timetabling System based on Graph Colouring and Constraint Manipulation. "Journal of Research on Computing in Education", Volume 27 Issue 1, 1994.
• Burke E.K., MacCarthy B.. Petrovic S., Qu R.: Structured cases in case-based reasoning - reusing and adapting cases for time-tabling problems. Knowledge-Based Systems 13, 2000.
• Burke E.K., Newall J.P., Weare R.F.: A Simple Heuristically Guided Search for the Timetable Problem. Proceedings of the International ICSC Symposium on Engineering of Intelligent Systems. ICSC Academic Press, Nottingham. 1998.
• Come D., A P.: Peckish Initialisation Strategies for Evolutionary Timetabling. Proceedings of the First International Conference on the Theory and Practice of Automated Timetabling, Napier University, Edinburgh, 1995.
• Čangalović M., Kovačević-Vujčić V., Ivanovć L., Dražić M.: Modeling and solving a real-life assignment problem at universities. European Journal of Operational Research 110, 1998.
• Colorni A., Dorigo M., Maniezzo V.: Genetic Algorithms and Highly Constrained Problems: the Time-Table Case. Proceedings of the First International Workshop on Parallel Problem Solving from Nature, Lecture Notes in Computer Science 496, 1990.
• Colorni A., Dorigo M., Maniezzo V.: Genetic Algorithms: a New Approach to the Time-Table Problem. Lecture Notes in Computer Science - NATO ASI Series, Vol. F 82, Combinatorial Optimalization, 1990.
• Colorni A., Dorigo M., Maniezzo V.: A Genetic Algorithm to Solve the Timetable Problem. Tech. rep. 90-060, Politecnico di Milano 1992.
• Dimopoulou M., Militois P.: Implementation of a university course and examination timetabling system. "European Journal of Operational Research" 130, 2001.
• Foulds L.R., Johnson D.G.: SlotManager: a microcomputer-based decision support system for university timetabling. Decision Support Systems 27, 2000.
• Hilton A.J.W., Slivnik T., Stirling D.S.G.: Aspects of edge list-colourings. "Discrete Mathematics", 231, 2001.
• Kaneko K., Yoshikawa M., Nakakuki Y.: Improving a Heuristic Repair Method for Large-Scale School Timetabling Problems. Springer-Verlag Principles and Practice of Constraint Programming - CP '99, 2000.
• Legierski W.: Programowanie z ograniczeniami metoda rozwiązywania problemu układania rozkładu zająć. Materiały V Konferencji Naukowej "Sztuczna inteligencja", Wydawnictwo Akademii Podlaskiej, Siedlce 2002.
• Shie-Jue Lee, Chih-Hung Wu: CLXPERT: A Rule-Based Scheduling System. Expert Systems With Applications, Vol. 9, No. 2, 1995.
• Mausser H.E., Magazine M.J.: Comparision of neural and heuristic methods for a timetabling problem. "European Journal of Operational Research" 93, 1996.
• Michalewicz Z.: Algorytmu genetyczne + struktury danych = programy ewolucyjne. Wydawnictwa Naukowo-Techniczne, Warszawa 1999.
• Newall J.P.: Hybrid Methods for Automated Timetabling, PhD Thesis. Department of Computer Science. University of Nottingham 1999.
• Norberciak M.: Algorytm ewolucyjny w rozwiązywaniu silnie ograniczonego, rozległego problemu planowania. Materiały V Konferencji Naukowej "Sztuczna inteligencja", Wydawnictwo Akademii Podlaskiej, Siedlce 2002.
• Norberciak M.: Przegląd metod automatycznego planowania - przykład wykorzystania algorytmu genetycznego w rozwiązaniu prostego problemu planowania. "Prace Naukowe Wydziałowego Zakładu Informatyki Politechniki Wrocławskiej", Sztuczna Inteligencja nr 1, Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław 2002.
• Ross P., Corne D.: Comparing Genetic Algorithms, Simulated Annealing, and Stochastic Hillclimbing on Timetabling Problems. Evolutionary Computing; AISB Workshop, Sheffield 1995, Selected Papers, T. Fogarty, Springer-Verlag Lecture Notes in Computer Science 993, 1995.
• Ross P., Corne D., Hsiao-Lan Fang.: Successful Lecture Timetabling with Evolutionary Algorithms. Workshop Notes, ECAI'94 Workshop 1994.
• Schaerf A.: A Survey of Automated Timetabling. Tech. rep. CS-R9567, CWI, Amsterdam 1995.
• Schaerf A.: Tabu Search Techniques for Large School Timetabling Problems Tech. rep. CS-R9611, CWI, Amsterdam 1996.
• Thompson J.M., Dowsland K.A.: A Robust Simulated Annealing Based Examination Timetabling System. "Computers Ops Research", Vol. 25, No. 7/8, 1998.
• Weare R.F.: Automated Examination Timetabling, PhD Thesis, Department of Computer Science, University of Nottingham 1995.
• de Werra D.: Extensions of coloring models for scheduling purposes. "European Journal o Operational Research" 92, 1996.
• de Werra D.: The combinatorics of timetabling. "European Journal of Operational Research" 96, 1997.
• de Werra D.: Restricted coloring models for timetabling. "Discrete Mathematics" 165/166,1997.
• de Werra D.: On a multiconstrained model for chromatic scheduling. "Discrete Applied Mathematics" 94, 1999.
• de Werra D., Mahadev N.V.R.: Preassignment requirements in chromatic scheduling. "Discrete Applied Mathematics" 76, 1997.