-
آرشیو :
نسخه زمستان 1397
-
موضوع :
هوش مصنوعی
-
نویسنده/گان :
علیرضا محسنی ، ونوس مرضی، امیرحسین جدیدی نژاد
-
چکیده :
در سالهای اخیر نرخِ رشدِ اطلاعات، بسیار فزاینده بوده و نیاز به سیستمهای خلاصهساز متن احساس میشود. خلاصهسازي خودکار سند به معنی توليد يک نسخه مختصرتر از سند اصلي با حفظ نکات کلیدی به وسیله کامپیوتر میباشد. روشهای مختلفی جهت خلاصهسازی متون فارسی تاکنون به کار گرفته شده است که از روشهای استخراجی استفاده مینمایند که در این روش جملات مهم براساس الگوریتمهایی استخراج و به یکدیگر متصل میگردند همچنین در آخرین روشها برای بهبود نتایج از یادگیری ماشینی استفاده شده ، لذا تاکنون در زمینهی خلاصهسازی به کمک یادگیری عمیق ماشینی کمتر کاری انجام شده است. یادگیری عمیق ماشینی از شبکههای عصبی عمیق مصنوعی استفاده مینماید که نتایج بسیار خوبی در مقایسه با روشهای مرسوم از خود نشان داده است. ما جهت خلاصهسازی متون فارسی از شبکههای عمیق انکودر-دکودر استفاده نمودیم که این دسته از شبکهها قابلیت بالایی در استخراج ویژگی دارا میباشند. ما جهت ایجاد زیرساختهای نرم افزاری لازم از آخرین فناوری شرکت گوگل یعنی تنسورفلو استفاده نمودیم همچنین یکی از دستاوردهای این تحقیق توسعه یک دیتاست فارسی سازگار با مدل نهایی ما بر پایه مجموعه همشهری می باشد و بر اساس آن شبکه خود را آموزش دادیم.
واژگان کليدي: خلاصهسازی خودکار متن، تسورفلو، یادگیری عمیق، شبکه عصبی، انکودر-دکودر، شبکه عصبی بازگشتی. مسأله جدول زمانبندی دروس دانشگاهی، یک فرآیند زمانبندی دروس دانشگاهی برای یک نیم سال تحصیلی توسط دانشکده¬های یک دانشگاه می¬باشد که ذاتا مسأله¬ای است در گروه مسائل سخت از نوع دسته¬ی مسائل NP-Complete. این مسأله رویدادها (استادان/دانشجویان/دروس) را در منابع (برش¬های زمانی/ کلاس¬های درسی) زمانبندی و تخصیص می¬دهد که این فرآیند تخصیص دارای دو قید حساس می¬باشد که این قیود سخت و نرم می¬باشند. هدف مسأله بهبود قیود نرم می¬باشد. در این مقاله، رهیافت¬های مورد بررسی برای زمانبندی استادان (مشترک مابین) دانشکده¬(ها) شامل، الگوریتم¬های خوشه¬بندی (K- میانگین، C- میانگین فازی و قیفی)، مقایسه¬ی تصمیم گیری چند معیاره¬ی فازی، ترکیبی (جستجوی محلی/ ژنتیک) و ترکیب الگوریتم¬های خوشه¬¬بندی با مقایسه¬ی تصمیم گیری چند معیاره¬ی فازی با ترکیبی می¬باشد. البته بهینگی و مقایسه¬ی کارآیی عملکرد الگوریتم¬های به کار گرفته شده در این مقاله به طور کامل مورد تحلیل و بررسی دقیق قرار گرفته است.
-
کلید واژه :
جدول زمانبندی دروس دانشگاهی، الگوریتم¬های خوشه¬بندی، الگوریتم مقایسه¬ی تصمیم گیری چند معیاره¬ی فازی و الگوریتم ترکیبی.
-
Title :
A New Approach to Solve University Course Timetabling Problem
-
Abstract :
University Course Time-Tabling Problem is a process of scheduling university courses for one semester by the faculties of a university, which is inherently NP-Complete problem. The main technique in the presented approach is focused on developing and making the process of timetabling common lecturers among different departments of a university scalable. This problem schedules and allocates events (lecturers/ students/ courses) to resources (time slots/ classrooms), which has two sensitive constraints including hard and soft constraints. The goal is to improve soft constraints. In this paper, the studied approaches include clustering algorithms (K-means, fuzzy C-means, and funnel), fuzzy multi-criteria decision making comparison, hybrid (local search/ genetic) and combination of clustering algorithms with fuzzy multi-criteria decision making comparison. For this, the optimization and performance comparisons of the algorithms used in this paper are thoroughly analyzed. Paper’s aims: 1) descending satisfaction of preferences and soft constraints of common lecturers among departments, 2) minimizing the loss of extra resources of each faculty. An applied dataset is based on meeting the requirements of scheduling in real world, among various departments of Islamic Azad University, Ahar Branch and the success of the results would be in respect of satisfying uniform distribution and allocation of common lecturers on extra resources among different departments.
-
مراجع :
[1] Obit, J. H., Developing Novel Meta-heuristic, Hyper-heuristic and Cooperative Search for Course Timetabling Problems, Ph.D. Thesis, School of Computer Science University of Nottingham, 2010.
[2] Gotlib, C. C., "The Construction of Class-Teacher TimeTables", Proc IFIP Congress, Vol. 62, pp. 73-77, 1963.
[3] Asmuni, H., Fuzzy Methodologies for Automated University Timetabling Solution Construction and Evaluation, Ph.D. Thesis, School of Computer Science University of Nottingham, 2008.
[4] Lewis, M. R., Metaheuristics for University Course Timetabling, Ph.D. Thesis, Napier University, 2006.
[5] Redl, T. A., A Study of University Timetabling that Blends Graph Coloring with the Satisfaction of Various Essential and Preferential Conditions, Ph.D. Thesis, Rice University, Houston, Texas, 2004.
[6] Babaei, H., Hadidi, A., "A Review of Distributed Multi-Agent Systems Approach to Solve University Course Timetabling Problem", ACSIJ Advances in Computer Science: an International Journal, Vol. 3, Issue 5, No. 11, ISSN: 2322-5157, pp. 19-28, 2014.
[7] Feizi-Derakhshi, M. R., Babaei, H., Heidarzadeh, J., "A Survey of Approaches for University Course TimeTabling Problem", Proceedings of 8th International Symposium on Intelligent and Manufacturing Systems, Sakarya University Department of Industrial Engineering, Adrasan, Antalya, Turkey, pp. 307-321, 2012.
[8] Babaei, H., Karimpour, J., Hadidi, A., "A survey of approaches for university course timetabling problem", Computers & Industrial Engineering, 86, pp. 43–59, 2015.
[9] Obit, J. H., Landa-Silva, D., Ouelhadj, D., Khan Vun, T., Alfred, R., "Designing a Multi-Agent Approach System for Distributed Course TimeTabling," IEEE, 2011.
[10] Shatnawi, S., Al -Rababah, K., Bani-Ismail, B., "Applying a Novel Clustering Technique Based on FP- Tree to University Timetabling Problem: A Case Study," IEEE, 2010.
[11] Wangmaeteekul, P., Using Distributed Agents to Create University Course TimeTables Addressing Essential Desirable Constraints and Fair Allocation of Resources, Ph.D. Thesis, School of Engineering & Computing Sciences Durham University, 2011.
[12] Amintoosi, M., Haddadnia, J., "Fuzzy C-means Clustering Algorithm to Group Students in A Course into Smaller Sections," Springer-Verlag Berlin Heidelberg, LNCS 3616, pp. 147–160, 2005.
[13] S. Srinivasan, J. Singh, V. Kumar, "Multi-Agent based Decision Support System Using Data Mining and Case Based Reasoning", IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 2, July 2011.
[14] DeWerra, D., "An Introduction to TimeTabling", European Journal of Operational Research, 19: pp. 151-162, 1985.
[15] Asham, G.M., Soliman, M.M., Ramadan, A.R., "Trans Genetic Coloring Approach for Timetabling Problem", Artificial Intelligence Techniques Novel Approaches & Practical Applications, IJCA, pp. 17-25, 2011.
[16] Daskalaki, S., Birbas, T., Housos, E., "An integer programming formulation for a case study in university timetabling", European Journal of Operational Research, 153 (2004), pp. 117–135, 2004.
[17] Daskalaki, S., Birbas, T., "Efficient solutions for a university timetabling problem through integer programming”, European Journal of Operational Research, 160 (2005), pp. 106–120, 2005.
[18] Khonggamnerd, P., Innet, S., "On Improvement of Effectiveness in Automatic University Timetabling Arrangement with Applied Genetic Algorithm", 978-0-7695-3896-9, IEEE, 2009.
[19] Alsmadi, O. MK., Abo-Hammour, Z. S., Abu-Al-Nadi, D. I., Algsoon, A., "A Novel Genetic Algorithm Technique for Solving University Course Timetabling Problems", 978-1-4577-0690-5/11, IEEE, 2011.
[20] Mayer, A., Nothegger, C., Chwatal, A., Raidl, G., "Solving the Post Enrolment Course Timetabling Problem by Ant Colony Optimization”, In Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling, 2008.
[21] Ayob, M., Jaradat, G., "Hybrid Ant Colony Systems For Course Timetabling Problems", 2nd Conference on Data Mining and Optimization 27-28 October 2009, Selangor, Malaysia, IEEE, pp. 120-126, 2009.
[22] Jat, N. S., Shengxiang, Y., "A Memetic Algorithm for the University Course Timetabling Problem", 20th IEEE International Conference on Tools with Artificial Intelligence, IEEE, pp. 427-433, 2008.
[23] Alvarez, R., Crespo, E., Tamarit, J. M., "Design and Implementation of a Course Scheduling System Using Tabu Search", European Journal of Operational Research 137, pp. 512-523, 2002.
[24] Aladag, C. H., Hocaoglu, G., Basaran, A. M., "The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem", Expert Systems with Application, 36 (2009), pp. 12349–12356, 2009.
[25] Tuga, M., Berretta, R., Mendes, A., "A Hybrid Simulated Annealing with Kempe Chain Neighborhood for the University Timetabling Problem", 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007), 2007.
[26] Shengxiang, Y., Jat, N.S., "Genetic Algorithms with Guided and Local Search Strategies for University Course Timetabling", IEEE Transactions on Systems, MAN, and Cybernetics-PART C: Applications and Reviews, Vol. 41, No. 1, January 2011.
[27] Abdullah, S., Burke, E.K., McColloum, B., "An Investigation of Variable Neighborhood Search for University Course Timetabling", In The 2th Multidisciplinary Conference on Scheduling: Theory and Applications, NY, USA, pages 413-427, 2005.
[28] Kostuch, P., "The University Course Timetabling Problem with a Three-Phase Approach", In Lecture Notes in Computer science, pages 109-125, Springer-Berlin / Heidelberg, 2005.
[29] Shahvali Kohshori, M., Abadeh, M. S., "Hybrid Genetic Algorithms for University Course Timetabling", IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 2, No 2, March 2012.
[30] Asmuni, H., Burke, E.K., Garibaldi, J.M., "Fuzzy multiple heuristic ordering for course timetabling", The Proceedings of the 5th United Kingdom Workshop on Computational Intelligence (UKCI05), London, UK, pp 302-309, 2005b.
[31] Golabpour, A., Mozdorani Shirazi, H., Farahi, A., kootiani, M., beige, H., "A fuzzy solution based on Memetic algorithms for timetabling", International Conference on MultiMedia and Information Technology, IEEE, pp. 108-110, 2008.
[32] Chaudhuri, A., Kajal, D., "Fuzzy Genetic Heuristic for University Course Timetable Problem", Int. J. Advance. Soft Comput. Appl., Vol. 2, No. 1, ISSN 2074-8523, March 2010.
[33] Gaspero, L.D., Missaro, S., Schaerf, A., “A Multi-agent Architecture for Distributed Course Timetabling", Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling (PATAT '04), pp. 471-474, 2004.
[34] Meisels, A., Kaplansky, E., "Scheduling Agents-Distributed TimeTabling Problems (DisTTP)", Springer- Verlog Berlin Heldelberg, LNCS 2740, PP. 166 – 177, 2003.
[35] Nandhini, M., Kanmani, S., "Implementation of Class Timetabling Using Multi Agents", 978-1-4244-4711-4/09, IEEE, 2009.
[36] Yanga, Y., Paranjape, R., "A multi-agent system for course timetabling", Intelligent Decision Technologies, Computer Science and Artificial Intelligence, IOS Press, Volume 5, page 113-131, Number 2, 2011.
[37] Babaei, H., Karimpour, J., Oroji, H., "Using fuzzy c-means clustering algorithm for common lecturers timetabling among departments", 6th International Conference on Computer and Knowledge Engineering (ICCKE 2016), 978-1-5090-3586 IEEE, October 20-21, Ferdowsi University of Mashhad, 2016.
[38] Babaei H., Karimpour J., Hadidi A., "Common lecturers timetabling among departments based on funnel-shape clustering algorithm", Springer Science + Business Media New York, Applied Intelligence, DOI 10.1007/s10489-016-0828-5, 46: pp. 386-408, 2017.
[39] Babaei H., Karimpour J., Mavizi S., "Using k-means clustering algorithm for common lecturers timetabling among departments”, ACSIJ Advances in Computer Science: an International Journal, Vol. 5, Issue 1, No.19, ISSN: 2322-5157, pp. 86-102, 2016.
[40] Ross, J. T., Fuzzy logic with engineering applications. Wiley, University of New Mexico, New Mexico, 2004.
[41] Babaei, H., Karimpour, J., Hadidi, A., "Applying Hybrid Fuzzy Multi-Criteria Decision-Making Approach to Find the Best Ranking for the Soft Constraint Weights of Lecturers in UCTP", Int. J. Fuzzy Syst. Taiwan Fuzzy Systems Association and Springer -Verlag Berlin Heidelberg, 2017.
[42] Babaei H., Karimpour J., Hadidi A., "Generating an optimal timetabling for multi-departments common lecturers using hybrid fuzzy and clustering algorithms", Springer-Verlag GmbH Germany, Soft Computing, doi.org/10.1007/s00500-018-3126-9, Volume 23, Issue 13, pp 4735–4747, 2019.
[43] Babaei H., Hadidi A., "Generating optimal timetabling for lecturers using hybrid fuzzy and clustering algorithms", Journal of Artifical Intelligence in Electrical Engineering, Vol. 6, No. 21, 2017.
- صفحات : 1-16
-
دانلود فایل
( 1.28 KB )