بخشی از مقاله
چکیده :
می دانیم که کتابخانهها یک منبع مهم برای جوامع علمی به شمار می آیند. نحوهی دسترسی به کتابها در داخل کتاب خانه مهم است. چیدمان کتابها تأثیر زیادی در دسترسی به کتابها دارد. درواقع با تغیر در چیدمان کتابها، نحوه ی دسترسی نیز تغیر خواهد کرد. بنابراین مسئله چیدمان، یک مسئله مکانی است. موقعیت قفسه ها، حجم قفسه ها، شباهت موضوعی کتاب ها، اهمیت کتاب ها برای مراجعین، در نحوه ی دسترسی تأثیرگذار هستند. برای دسترسی بهتر، روشهایی ارائه شده اند که هرکدام از آن ها نواقصی دارند و ممکن است چیدمان را بهینه نکنند.
با توجه به تعداد حالات زیاد چیدمان و محدودیتهای ذکرشده، امکان حل مسئله توسط روشهای قطعی و ریاضی وجود ندارد. هدف اصلی این است که با استفاده از الگوریتم رقابت استعماری، کتاب ها را طوری در قفسههای کتاب خانه بچینیم، که حرکت کلیه ی مشتری ها در مجموعه ی کتابخانه کمینه شود. الگوریتم بر روی یک کتابخانه فرضی و یک کتابخانه واقعی پیاده سازی شده است.
چیدمان به دست آمده از الگوریتم با چیدمان موجود در کتابخانه واقعی و همچنین با چیدمان به دست آمده از سایر الگوریتم های فرا ابتکاری مقایسه شده است. نتایج محاسبات نشان می دهد که نحوه ی دسترسی در چیدمان به دست آمده نسبت به چیدمان فعلی موجود در کتابخانه راحت تر است. همچنین الگوریتم دارای دقت، سرعت همگرایی و تکرارپذیری بالایی است و برای مسئله تخصیص بهینه فضای کتاب خانه به انواع کتاب، مناسب است. برای واقعی تر شدن مسئله می توان، چیدمان قفسه ها را نیز بهینه کرد و قیود یا پارامترهای دیگری را نیز در نظر گرفت و چیدمان بهتری را ارائه نمود.
-1 مقدمه
همان طور که میدانیم، کتابخانه ها یک منبع مهم برای جوامع علمی به شمار میآیند. نحوهی دسترسی به کتاب ها در داخل یک کتابخانهی بزرگ مهم است که ارتباط مستقیمی با نحوه ی چیدن کتابها دارد. درواقع با تغیر در چیدمان کتاب ها، نحوهی دسترسی به کتابها نیز تغیر خواهد کرد. بنابراین مسئله چیدمان، یک مسئله مکانی است. فواصل قفسهها از همدیگر، ابعاد کتابخانه و حجم قفسهها در نحوهی دسترسی تأثیرگذار هستند
برای دسترسی بهتر به کتاب ها روش هایی ارائه شده اند که هرکدام از آن ها نواقصی دارند. بنابراین ممکن است نحوهی دسترسی به کتاب ها بهینه نشود. در این تحقیق سعی بر این است که با استفاده از یک الگوریتم جدید فرا ابتکاری نحوهی دسترسی، بهینه یا نزدیک به بهینه شود. همچنین مشکلات روشهایی قبلی بهبود پیدا کنند.
-1-1 بیان مشکل
مسئله اصلی این است که چگونه کتاب ها را در قفسهها بچینیم، تا مراجعین مختلف با علایق متفاوت، در کمترین زمان به آن ها دسترسی پیدا کنند. حل این مسئله، مستلزم داشتن اطلاعات موردنیاز، از قبیل اهمیت کتاب برای مشتری و رابطه ی بین کتابها است.
بهتر است کتابهای که مراجعین بیشتری دارند، نزدیکتر به درب ورودی کتابخانه باشند. تا دسترسی به آن ها آسان باشد و از ازدحام مشتری و هدر رفتن زمان جلوگیری کند. همچنین بهتر است که رابطهی بین کتابها باهم، در چیدمان لحاظ شود. مثلاً کسی که به کتاب فیزیک علاقه دارد، بهاحتمال بیشتری میزان علاقهاش به کتاب ریاضی، بیشتر از میزان علاقهاش به کتاب تاریخ است. بنابراین بهتر است که کتاب ریاضی و فیزیک در قفسههای نزدیک تر به هم، چیده شوند. این دو موضوع در شکل - 1 - نشان دادهشده است. با فرض اینکه کتاب A دارای اهمیت بیشتری نسب به سایر کتاب ها برای مراجعین باشد. همچنین کتاب های B و C نیز تا حدودی به آن وابسته باشند. به این معنی کهمثلاً 70 درصد از مراجعین کتاب A خواهان کتاب B و C نیز باشند
با توجه به شکل -1 - الف - ، میتوان نتیجه گرفت که اگر این سه نوع کتاب در فاصلههای دور از هم قرار داشته باشند مراجعهکننده باید مسیر بیشتری را برای دسترسی به کتاب طی کند. ولی اگر نزدیک به همدیگر قرار داشته باشند مراجعهکننده مسیر کمتری را طی خواهد کرد - شکل -1 - ب - - . همچنین اگر علاوه بر اینکه کتاب ها نزدیک به همدیگر باشند، نزدیک درب ورودی نیز باشند. در این حالت نیز مراجعه کننده مسیر کمتری را طی خواهد کرد. درنتیجه مسئله چیدمان یک مسئله مکانی است که با تغییر موقعیت کتابها نحوهی دسترسی تغییر خواهد کرد.
شکل:1 نحوهی دسترسی به کتاب در چیدمانهای متفاوت الف - چیدمان بد ب - چیدمان خوب
اگر یک کتابخانه شامل20 قفسه و 10 نوع کتاب باشد، با تعداد حالات بسیار زیاد می توان کتابها را در قفسهها چید. علاوه بر تعداد حالات بسیار زیاد، اهمیت کتاب برای مشتری و رابطهی بین کتابها، عوامل دیگری از قبیل فضای قفسه ها، فاصلهی بین قفسهها، ابعاد کتابخانه، حجم قفسهها و... مهم هستند و بهتر است که لحاظ شوند.
بنابراین مسئله ی چیدمان یک مسئله ی پیچیده است و روش های ریاضی نمی توانند جواب بهینهای برای مسئله در زمان قابل قبول پیدا کنند. همچنین در روش های تحلیلی چیدمان برای تمام کتابخانها به یک صورت است و لزوماً چیدمان بهینه نیستند. همچنین محدودیت های ذکرشده، در نظر گرفته نشده است. معمولاً برای حل مسائل بهینهسازی با فضای جستجوی وسیع و شروط پیچیده، از الگوریتمهای فرا ابتکاری استفاده میشود، که میتوانند جوابهای نزدیک به جواب بهینه را، در زمان قابلقبول به دست بیاورند.
-2-1 اهداف تحقیق
هدف اصلی این است که با استفاده از الگوریتم رقابت استعماری1 با در نظر گرفتن شباهت موضوعی کتابها، اهمیت کتابها برای مراجعین، موقعیت قفسهها، کتابها را طوری در قفسه ها ی کتاب خانه بچینیم، که حرکت کلیهی مشتریها در مجموعهی کتابخانه کمینه شود. همچنین علاوه بر موقعیت قفسهها, ارتفاع و تعداد طبقات آن نیز مهم است که نشاندهندهی سهبعدی بودن مسئله است.[5] اما در این تحقیق، برای سادهسازی مسئله، فرض میکنیم که ارتفاع همهی قفسهها و تعداد طبقات آنها برابر است. درواقع، صورتمسئله را دوبعدی فرض میکنیم. حل این مسئله مستلزم طراحی و مدلسازی در قالب الگوریتم، تنظیم پارامترهای الگوریتم و پیادهسازی است.
-3-1 مروری بر تحقیقات انجامشده
چیدن کتاب ها در اکثر کتابخانه های دنیا از یک استاندارد مشخصی تبعیت می کند. در این زمینه رده بندیهایی وجود دارد که هر کتابخانه با توجه به علاقهمندی و تخصص خود از آنها استفاده میکند. در کتابخانههای ایران اکثر کتابخانه ها از دو رده بندی مشهور به نام ردهبندی کنگره2 آمریکا[6] و ردهبندی دیویی[7] استفاده میکنند. این روش ها شامل محدودیت های است که در بخش 1-1 به آنها اشارهشده است. همچنین مسئله چیدمان با الگوریتم بهینهسازی فاخته حل شده است[1]، که این الگوریتم نیز دارای محدودیت است که این محدودیت در الگوریتم استعماری وجود ندارد.
-1-3-1 دسته بندی مسائل بهینه سازی
بهینه سازی بر هر چه بهتر کردن راه حل مربوط به یک مسئله تأکید دارد که سعی دارد تا با تغییر دادن یک یا چند جواب ابتدایی بهسوی جواب بهینه حرکت کند. این مسیر حرکت ممکن است به جواب بهینه یا نزدیک به بهینه برسد.
تأکید بر وجود "بهترین" جواب مؤید وجود بیش از یک جواب برای مسائل است، که از ارزش یکسانی برخوردار نیستند. تعریف جواب بهینه به نوع مسئله، و روش حل آن بستگی دارد. بعضی از مسائل دارای جواب های بهینه کاملاً مشخص و یکتا هستند که تنها نیاز به شناسایی دارند. اما بعضی از مسائل علاوه بر این که ممکن است بیش از یک جواب بهینه داشته باشند، ممکن است جوابهای بهینه محلی نیز داشته باشند.
جهت انتخاب استراتژی مناسب برای حل مسائل بهینه سازی باید شناخت مناسبی از آن داشته باشیم. در این بخش میخواهیم انواع مسائل بهینه سازی را از دیدگاههای مختلف تقسیمبندی کنیم. مسائل بهینهسازی را از دیدگاههای مختلف به چندین نوع میتوان تقسیم بندی نمود.
-1بهینه سازی پیوسته و بهینه سازی گسسته: در یک مسئله گسسته مقادیر متغیرهای مسئله از یک مجموعه معین گسسته هستند.
