Approche d'Optimisation par Essaim de Bactéries pour les Problèmes de Planification de Cours Basés sur l'Inscription

Khalid Shaker • Salwani Abdullah • Arwa Alqudsi

Lien de l'Article  

Le problème de planification des cours universitaires est connu comme un problème NP-difficile. Il est également parfois connu comme un problème de planification de classes/enseignants qui fait référence à un ensemble de cours qui doivent être programmés dans un nombre donné de salles et de créneaux horaires au cours d'une semaine et, en même temps, les étudiants et les enseignants sont assignés aux cours afin que les réunions puissent avoir lieu. Une nouvelle approche basée sur la population est proposée dans cet article, appelée algorithme d'Optimisation par Essaim de Bactéries (BSO). Le BSO est développé sur la base du comportement des bactéries lorsqu'elles recherchent des nutriments. L'espace de recherche est divisé en trois régions, à savoir, les régions à risque, nulles et riches. L'algorithme d'Évolution Différentielle (DE) est intégré au BSO pour déplacer les solutions vers la meilleure solution. La performance de notre approche est testée sur onze ensembles de données de référence (représentant un problème grand, cinq moyens et cinq petits problèmes). Les résultats expérimentaux montrent que notre approche est capable de générer des résultats compétitifs par rapport aux approches précédemment disponibles. Des extensions possibles à cette approche simple sont également discutées.

Mots Clés : (BSO) algorithme , algorithme d'Évolution Différentielle

Références

1. Asaju La'aro Bolaji, Ahamad Tajudin Khader, Mohammed Azmi Al-Betar, Mohammed A. Awadallah : Planification des cours universitaires utilisant une colonie d'abeilles artificielles hybridée avec un optimiseur de montée de colline. J. Comput. Science 5(5) : 809-818 (2014)

2. Abdullah, S., Burke, E.K., McCollum, B. : Une approche évolutive hybride pour le problème de planification des cours universitaires. Congrès IEEE sur l'Informatique Évolutive, ISBN : 1-4244-1340-0, pp 1764-1768 (2007)

3. Abdullah, S., Burke, E.K., McCollum, B. : Une enquête sur la recherche de voisinage variable pour la planification des cours universitaires. La 2ème Conférence Internationale Multidisciplinaire sur la Planification : Théorie et Applications (MISTA), pp. 413–427 (2005)

4. Abdullah, S., Burke, E.K., McCollum, B. : Utilisation d'un algorithme d'amélioration itératif aléatoire avec des structures de voisinage composites pour la planification des cours universitaires. Dans Métaheuristiques : Progrès dans l'optimisation des systèmes complexes (Opérations de Recherche / Interfaces en Informatique), Chapitre 8. Publié par Springer, ISBN : 978-0-387- 71919-1 (2007)

5. Abdullah, S., Shaker, K., McCollum, B., McMullan, P. : Recuit Simulé à Séquence Double avec Approche Round-Robin pour la Planification des Cours Universitaires. EVOCOP 2010, LNCS 6022, Springer-Berlin /Heidelberg, pp 1–10 (2010)

6. Abdullah, S., Turabieh, H. : Génération de l'emploi du temps des cours universitaires utilisant des algorithmes génétiques et une recherche locale. La Troisième Conférence Internationale sur la Convergence et la Technologie de l'Information Hybride ICCIT, vol. I, pp 254-260 (2008)

7. Khalid Shaker, Salwani Abdullah, Arwa Alqudsi, Hamid Jalab : Hybridation des Approches Métaheuristiques pour Résoudre les Problèmes de Planification des Cours Universitaires. RSKT 2013 : 374-384, (2013)

8. Khalid Shaker, Salwani Abdullah, Arwa Hatem : Un Algorithme d'Évolution Différentielle pour le problème de planification des cours universitaires. DMO 2012 : 99-102, (2012)

9. Khalid Shaker & Salwani Abdullah : Contrôle de Multi Algorithmes Utilisant Round Robin pour le Problème de Planification des Cours Universitaires. FGIT-DTA/BSBT 2010 : 47-55, (2010)

10. M.A. Al-Betar, A.T. Khader, M. Zaman : Planification des cours universitaires utilisant un algorithme métaheuristique de recherche d'harmonie hybride, IEEE Trans. Syst. Man Cyber- net. C, Appl.Rev. doi.org/10.1109/TSMCC.2011.2174356, (2014)

11. Ghaith M. Jaradat, Masri Ayob : Un Système de Fourmis Élitiste pour Résoudre le Problème de Planification des Cours Post-Inscription. FGIT-DTA/BSBT 2010 : 167-176 (2010)

12. Shengxiang Yang, Sadaf Naseem Jat : Algorithmes Génétiques avec Stratégies de Recherche Guidée et Locale pour la Planification des Cours Universitaires. Transactions IEEE sur les Systèmes, l'Homme et la Cybernétique, Partie C 41(1) : 93-106 (2011)

13. Al-Betar, M., Khader, A., Yi Liao, I. : Une Recherche d'Harmonie avec un Taux d'Ajout de Multi-Pitch pour la Planification des Cours Universitaires. Dans : Z.W. Geem : Avancées Récentes dans l'Algorithme de Recherche d'Harmonie, SCI 270, pp. 147–161. Springer, Heidelberg (2010)

14. Burke, E., Eckersley, A., McCollum, B., Petrovic, S., Qu, R. : Approches hybrides de voisinage variable pour la planification des examens universitaires. Rapport Technique NOTTCSTR-2006-2, Université de Nottingham, École de CSiT (2006)

15. Burke, E.K., Meisels, A., Petrovic, S., Qu, R. : Une hyper-heuristique basée sur les graphes pour les problèmes de planification. European Journal of Operational Research 176, pp 177-192 (2007)

16. Landa-Silva, D., Obit, J.H. : Grande inondation avec un taux de déclin non linéaire pour résoudre le problème de planification des cours. La quatrième conférence internationale IEEE sur les Systèmes Intelligents. Varna, Bulgarie, pp. 8.11–8.18 (2008)

17. Lewis, R., Paechter, B. : Nouveaux opérateurs de croisement pour la planification avec des algorithmes évolutifs. Actes de la 5ème Conférence Internationale sur les Avancées Récentes en Informatique Douce (éd. Lotfi), Royaume-Uni, 16-18 décembre, pp 189-194 (2004)

18. Lewis, R. : Un aperçu des techniques basées sur les métaheuristiques pour les problèmes de planification universitaire. OR Spectrum 30, 167–190 (2008)

19. Malim, M.R., Khader, A.T., Mustafa, A. : Algorithmes Immunitaires Artificiels pour la Planification Universitaire. Dans : Burke, E.K., Rudova, H. (éd.) La 6ème Conférence Internationale sur la Pratique et la Théorie de la Planification Automatisée, Brno, République Tchèque, pp. 234–245 (2006)

20. McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A., Di Gaspero, L., Qu, R., Burke, E. : Établir l'Agenda de Recherche en Planification Automatisée : La Deuxième Compétition Internationale de Planification, Accepté pour publication dans le Journal INFORMS sur l'Informatique. doi 10.1287/ijoc.1090.0320 (2009)

21. McMullan, P. : Une mise en œuvre étendue de l'algorithme de grande inondation pour la planification des cours, Science Computationnelle – ICCS, Partie I, LNCS 4487, Springer-Verlag Berlin Heidelberg, pp 538–545 (2007)

22. Qu, R., Burke, E.K., McCollum, B., Merlot, L.T.G., et Lee, S.Y. : Un Aperçu des Méthodologies de Recherche et du Développement de Systèmes Automatisés pour la Planification des Examens. Journal of Scheduling, 12(1) : pp 55-89 (2009)