بخشی از مقاله
چکیده
مساله گالری هنری یکی از مشهورترین مسائل هندسه محاسباتی است. هدف این مساله قرار دادن حداقل تعداد نگهبان ها در گالری هنری است به نحوی که مجموع ناحیه حفاظت شده توسط آنها حداکثر باشد. با توجه به اینکه گالری هنری نوعی مساله بهینه سازی است الگوریتم های تکاملی می تواند برای حل آن بکار برده شود. یکی از این الگوریتم های تکاملی که در سالهای اخیر ارائه شده است، الگوریتم رقابت استعماری است که در حل مسائل بهینه سازی کارایی خوبی از خود نشان داده است. الگوریتم رقابت استعماری یک الگوریتم مبتنی بر جمعیت تصادفی است که از ایده تکامل سیاسی - اجتماعی بشر الهام گرفته است. در این مقاله روشی برای حل مساله گالری هنری با حداقل نگهبان با استفاده از الگوریتم رقابت استعماری ارائه شده است. نتایج شبیه سازی موفقیت روش پیشنهادی را برای حل مساله گالری هنری نشان می دهد.
واژههای کلیدی
مساله گالری هنری، هندسه محاسباتی، استراتژی های تکاملی، الگوریتم رقابت استعماری
-1 مقدمه
مساله گالری هنری برای اولین بار در سال 1973توسط ویکتور کلی برای عمده ترین بخش هایی که برای افراز مورد مطالعه قرار گرفته اند بخش نگهبان های ثابت به این ترتیب بیان شد که»کمترین تعداد نگهبان های های محدب، ستاره ای، حلزونی و یکنواست. برای چند ضلعی متعامد، لازم برای نگهبانی یک گالری هنری چه تعداد است؟.« از آن زمان تا کنون بخش های مربعی و مستطیلی مورد آزمایش قرار گرفته اند. [13] الگوریتم نمونه های مختلفی از این مساله مورد بحث و بررسی محققین قرار گرفته افرازی وجود دارد که چند ضلعی را به چند ضلعی ستاره ای تجزیه می کند
] .[ چاواتال اثبات کرد که نگهبان ثابت برای پوشش کامل و سپس هرنگهبان را در آن چند ضلعی قرار می دهد. اگر نگهبان درون است 1-8 هسته چند ضلعی ستاره ای قرار گیرد آن چندضلعی پوشش می یابد.[14]
چند ضلعی ساده P [ ] . در سالهای بعد اثبات ساده تری از این لازم است 9 الگوریتم هایی ارائه شده اند که ترکیبی از افراز و روش های ابتکاری را ] [ [ ] موضوع با استفاده از تکنیک های رنگ آمیزی ارائه شد 10 . در 11 نشان جهت افراز بهینه پیشنهاد می دهند. در[15] ابتدا چند ضلعی را مثلثداده شد که اگر نگهبان ها ثابت نباشند نگهبان نیاز است. یک الگوریتم با زمان تقریبی درجه دو پیشنهاد شده است که نقطه ای را درون بندی می کند و سپس به صورت تکراری قطرها را - برطبق یک روش چند ضلعی ساده p پیدا می کند که بزرگترین چند ضلعی رؤیت پذیر را ابتکاری - پاک می کند و دو سلول مجاور را ترکیب می کند تا زمانی که داشته باشد.
این الگوریتم یک الگوریتم تقریبی می باشد که به صورت هنوز ستاره ای باشد. یک روش طبیعی برای قرار دادن نگهبان ها، روش تصادفی و یکنواخت شروع به نمونه برداری - انتخاب نقاط درون - از چند حریصانه است. به این صورت که نگهبان ها تا پوشش کامل یکی یکی درون ضلعی می کند و ناحیه پوشش یافته توسط هر نقطه را از تعداد نمونه چند ضلعی قرار می دهیم. در [14] چندین الگوریتم ابتکاری برای مساله [ ] . مینیمم پوشش در این زمینه ارائه شده است و نتایج حاصل از اجرای آن ها هایی - نقاطی - در نظر می گیرد که این نقطه از آن رؤیت پذیر باشد 12 با استفاده از قرار دادن نگهبان ها بر روی مکان هایی که الگوریتم معین الگوریتم هایی وجود دارند که در جستجوی یک افراز بهینه از چند ضلعیمی باشند. باید توجه داشت که زمان اجرای آن ها چند جمله ای ست. کرده است بررسی شده است.
در این مقاله روش جدیدی برای حل مساله گالری هنری مبتنی برالگوریتم رقابت استعماری ارائه شده است که با استفاده از آن می توانیم تعداد ثابتی از نگهبان ها را روی سطح یک چند ضلعی قرار دهیم به نحوی که مجموع نواحی پوشش این نگهبان ها ماکزیمم گردد. ادامه این مقاله به شرح زیر سازماندهی می شود: در بخش دوم الگوریتم رقابت استعماری معرفی می شود. در بخش سوم برخی تعاریف پایه ارائه می گردد. بخش چهارم روش پیشنهادی ارائه می شود. بخش پنجم به نتایج روش پیشنهادی با استفاده از الگوریتم رقابت استعماری پرداخته و نهایتا بخش ششم مربوط به نتیجه گیری است.
-2 الگوریتم رقابت استعماری
الگوریتم رقابت استعماری - - ICA یک الگوریتم مبتنی بر جمعیت تصادفی است که از نظریه تکامل سیاسی - اجتماعی بشر الهام گرفته است و در زیر مجموعه الگوریتم های تکاملی دسته بندی می شود. در این الگوریتم راه حل های فضای مساله به صورت کشورهای استعمارگر و مستعمره در نظر گرفته می شود و کشورهای استعمارگر به همراه کشور های مستعمره به جستجوی نقاط بهینه برای حل مسائل بهینه سازی می پردازند. ICA اولین بار توسط آتش پز و کارلوکس معرفی شد.[16] در بهینه سازی، هدف یافتن یک جواب بهینه بر حسب متغیرهای مساله است. ابتدا آرایه ای از متغیرهای مساله که باید بهینه شوند، ایجاد می شوند. در الگوریتم رقابت استعماری این آرایه کشور نامیده می شود. در یک مسئله بهینه سازی بعدی، یک کشور، یک آرایه 1× بعدی است. این آرایه به صورت زیر تعریف می شود. هزینه یک کشور با ارزیابی تابع f در متغیرهای - P1, P2, P3,…, PN - یافته می شود.
بنابراینبا شروع الگوریتم، تعداد کشور اولیه ایجاد می شود. سپس به تعداد تا از بهترین اعضای این جمعیت - کشورهای دارای کمترین مقدار تابع هزینه - به عنوان امپریالیست انتخاب می گردد و باقیمانده کشورها به تعداد تا مستعمراتی را تشکیل می دهند که هر کدام به یک امپراتوری تعلق دارند. برای تقسیم مستعمرات اولیه بین امپریالیست ها، به هر امپریالیست، تعدادی از مستعمرات را که این تعداد، متناسب با قدرت آن امپریالیسم است، اختصاص پیدا می کند. برای انجام این کار، با داشتن هزینه همه امپریالیست ها، هزینه نرمالیزه آنها به صورت رابطه - - 3 در نظر گرفته می شود. که در آن ، هزینه امپریالیست n ام، بیشترین هزینه میان امپریالیست ها و ، هزینه نرمالیزه شده این امپریالیست می باشد. هر امپریالیستی که دارای هزینه بیشتری باشد، دارای هزینه نرمالیزه کمتری خواهد بود.
با داشتن هزینه نرمالیزه، قدرت نسبی نرمالیزه هر امپریالیست، بر اساس رابطه - 4 - محاسبه شده و بر مبنای آن، کشورهای مستعمره، بین امپریالیست ها تقسیم می شوند. از دیدگاه دیگر، قدرت نرمالیزه شده یک امپریالیست، نسبت مستعمراتی است که توسط آن امپریالیست اداره می شود. بنابراین تعداد اولیه مستعمرات یک امپریالیست برابر است با : که در آن ، تعداد اولیه مستعمرات یک امپراطوری و نیز تعداد کل کشورهای مستعمره موجود در جمعیت کشورهای اولیه است. round نیز تابعی است که نزدیک ترین عدد صحیح به یک عدد اعشاری را می دهد. با در نظر گرفتن برای هر امپراتوری، به این تعداد از کشورهای مستعمره اولیه به صورت تصادفی انتخاب کرده و به امپریالیست nام اختصاص می دهیم. قدرت کل یک امپراطوری برابر است با قدرت کشور استعمارگر، به اضافه درصدی از قدرت کل مستعمرات آن، بنابراین هزینه کل یک امپراطوری از رابطه - 5 - محاسبه می شود.
که در آن هزینه کل امپراطوری nام و عددی مثبت است که معمولا بین صفر و یک و نزدیک به صفر در نظر گرفته می شود. با داشتن حالت اولیه تمام امپراطوری ها، الگوریتم رقابت استعماری شروع می شود. مطابق شکل1 کشور امپریالیست کشور مستعمره را در راستای محورهای فرهنگ و زبان به سمت خود جذب می کند. کشور مستعمره به اندازه x واحد در جهت خط واصل مستعمره به استعمارگر حرکت کرده و به موقعیت جدید کشانده می شود. در این شکل، فاصله میان استعمارگر و مستعمره با d نشان داده شده است. همچنین x نیز عددی تصادفی با توزیع یکنواخت می باشد - رابطه . - 7که در آن عددی بزرگتر از یک و نزدیک به 2 می باشد . یک انتخاب مناسب می تواند باشد. وجود ضریب باعث میشود تا کشور مستعمره در حین حرکت به سمت کشور استعمارگر، از جهتهای مختلف به آن نزدیک شود.در الگوریتم رقابت استعماری انحراف احتمالی با افزودن یک زاویه تصادفی به مسیر جذب مستعمرات، انجام می گیرد. شکل1 این حالت را نشان می دهد.
بدین منظور این بار به جای حرکت به اندازه x، به سمت کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، به همان میزان، ولی با انحراف در مسیر، به حرکت خود ادامه می دهیم. در رابطه - - 8، پارامتری دلخواه میباشد که افزایش آن باعث افزایش جستجوی اطراف امپریالیست شده و کاهش آن نیز باعث میشود تا مستعمرات تا حد ممکن، به بردار واصل مستعمره به استعمارگر، نزدیک حرکت کنند. با در نظر گرفتن واحد رادیان برای ، عددی نزدیک به ، در اکثر پیاده سازی ها، انتخاب مناسبی بوده است. در الگوریتم رقابت امپریالیست ها یک قانون مهم است. و آن اینکه به مرور زمان، امپراطوری های ضعیف، مستعمرات خود را از دست داده و امپراطوری های قویتر، این مستعمرات را تصاحب کرده و بر قدرت خویش می افزایند. برای مدل سازی رقابت میان امپراطوری ها برای تصاحب این مستعمرات، ابتدا احتمال تصاحب هر امپراطوری، با در نظر گرفتن هزینه کل امپراطوری، بر اساس رابطه - 9 - محاسبه می شود. در این رابطه T.C.، هزینه کل امپراطوری nام و نیز، هزینه کل نرمالیزه شده آن امپراطوری می باشد. با داشتن هزینه کل نرمالیزه شده، احتمال تصاحب مستعمره رقابت، توسط هر امپراطوری، از رابطه - - 10 محاسبه می شود. پس از مدتی، همه امپراطوری ها، سقوط کرده و تنها یک امپراطوری باقی خواهد ماند و بقیه کشورها تحت کنترل این امپراطوری واحد، قرار خواهند گرفت.
-3 تعاریف
چند ضلعی ورودی یک چند ضلعی ساده با n رأس می باشد. را یک چند ضلعی ساده گویند اگر ضلع های غیر متوالی همدیگر را قطع نکنند. در واقع این چند ضلعی صفحه را به دو ناحیه ی محدود - داخل چند ضلعی - و نا محدود - خارج چند ضلعی - تقسیم می کند. دو نقطه برای یکدیگر رؤیت پذیرند اگر پاره خطی که این دو نقطه را به هم وصل می کند کاملا درون چند ضلعی قرار بگیرد.[1] چند ضلعی رؤیت پذیری از نقطه درون چند ضلعی عبارت است از تمام رئوس که از نقطه ی قابل رؤیت هستند.[1] به طور مشابه برای مجموعهنقاط ،اجتماع تمام چندضلعی های رؤیت پذیری مجموعه نقاط عبارت از است.[17] هدف این مساله این است که در چند ضلعی ساده داده شده نگهبان ها درون چند ضلعی به نحوی قرار گیرند که با حداقل تعداد نگهبان، ناحیه حفاظت شده توسط آنها حداکثر باشد. در این مقاله پیش فرض هایی کلی جهت حل مساله ماکزیمم کردن ناحیه حفاظت شده یک گالری هنری به صورت زیر در نظر گرفته شده است :
- چندضلعی ورودی چند ضلعی ساده است.
- دید نگهبان ها نامحدود است.
- نگهبان ها چرخش 360 درجه دارند.
-4 روش پیشنهادی
-1-4 ایجاد جمعیت اولیه
الگوریتم رقابت استعماری مانند هر الگوریتم تکاملی دیگری نیاز به یک جمعیت اولیه دارد که در اینجا جمعیت اولیه همان کشورها هستند. هر کشور عبارت است از یک راه حل ممکن برای حل مسأله، پس برای مسأله ی ماکزیمم پوشش، هر کشور بایستی شامل مختصات محل قرار گیری k نگهبان در چند ضلعی باشد. برای ایجاد جمعیت اولیه نیاز به روشی است که بتواند تعدادی نقاط تصادفی درون چند ضلعی تولید نماید؛ برای تولید نقاط تصادفی در چند ضلعی، ابتدا چند ضلعی با استفاده از الگوریتم های معمول مثلث بندی، مثلث بندی می شود و سپس نقاط تصادفی درون مثلث ها تولید می شوند.[18]
2-4 -تابع هزینه
در حقیقت برای حل یک مساله بهینه سازی، الگوریتم رقابت استعماری به دنبال بهترین کشور می باشد . برای ساخت هر کشور، k نقطه تصادفی به تعداد موقعیت های تشکیل دهنده کشور، از بردار حاوی نقاط تصادفی تولید شده در چند ضلعی، انتخاب می شود. یافتن این کشور معادل یافتن بهترین پارامترهای مساله است که کمترین مقدار تابع هزینه را تولید می کنند. در مساله گالری هنری این تابع عبارت است از درصد دیدی که توسط موقعیت هر کشور حاصل می شود. همان طور که گفته شد هر کشور نشان دهنده ی چند موقعیت در چند ضلعی است. تابع هزینه عبارت است از درصد دیدی که توسط مجموع موقعیت های هر کشور حاصل می شود. پس مقدار هزینه یک کشور برابر است با مجموع هزینه ی موقعیت های آن کشور. برای تعیین هزینه یک موقعیت، موقعیت هر کشور درون چند ضلعی و رئوس آن بررسی خواهد شد. زمانی رأس و موقعیت کشور به هم دید دارند که پاره خط متصل کننده آن رأس و موقعیت کشور را هیچ نقطه ای قطع نکند . برای مثال همانطورکه در شکل 3 مشاهده می شود اگر b نقطه ی مورد نظر در چند ضلعی، a یکی از رئوس چند ضلعی و پاره خط متصل کننده ی این دو D باشد؛ در صورتی a وb به هم دید دارند که هیچ کدام از اضلاع چند ضلعی میان این دو نباشند یا به عبارتی با خط D
