بخشی از مقاله
چکیده -
شبکه حس گر بی سیم - WSN - متشکل از تعداد زیادی از حس گر ها است و هر یک از آن ها همانگونه که از اسم شان مشخص است، قادر به تشخیص در محدوده ی میدان حس کنندگی شان - Rsense - هستند و همچنین می توانند در محدوده ارتباطی شان - Rcom - مخابره داشته باشند. محدودیت در اندازه، انرژی و حافظه آن ها موانعی را ایجاد می کند که باعث می شوند نتوانند مستقیما اطلاعات را به واحد پردازنده اطلاعات - CPU - ارسال کنند. بنابراین تمام اطلاعات حس شده در گره خاصی گردآوری می شوند که به آن گره ی مخابره انرژی بالا - HECN - گفته می شود و سپس به DPU انتقال داده می شوند.
حس گر ها نمی توانند اطلاعات را به طور مستقیم به HECN ارسال کنند. به همین دلیل آنها باید اطلاعات را به یکی از حس گر های همسایه ارسال کنند - آن ها یی که در محدوده ی مخابراتی هستند - و این فرآیند ادامه دارد تا آن جایی که اطلاعات به HECN برسد.کیفیت چنین شبکه ای قواًی متاثر از موقعیت گره های حس گر ها در نواحی مورد علاقه است. در حقیقت، اهداف دوگانه از پیاده سازی هر حس گر شبکه چنان است که تمام اهداف مناسب پوشش داده شود به طوری که شبکه نیز برای مدت زمان طولانی موثر کارگر باشد. این اهداف، چند اندازه کیفیت برای شبکه WSN توضیح داده شده در دو بخش بعدی تعریف می شوند.
کلید واژه- شبکه حسگر بیسیم، الگوریتم های تکاملی.
-1 مقدمه
به طور کلی بهینه سازی به معنای یافتن یک و یا چند پاسخ مجاز در ارتباط با یک و چند هدف می باشد. نیاز به یافتن چنین پاسخهایی در یک مساله واقعی،عموما در ارتباط با کمینه کردن هزینه ها،بیشینه کردن قابلیت اعتماد و از این دست می باشد. به علت وجود چنین نیازهایی ،تکنیکهای بهینه سازی دارای نقش بسیار مهمی ،در رشته های مهندسی ،آزمایشات علمی و تصمیم گیری های تجاری می باشند.زمانی که یک مساله بهینه سازی یک سیستم فیزیکی که تنها شامل یک تابع هف است را مدل می نماید، عمل یافتن پاسخ بهینه ،دراصطلاح بهینه سازی تک هدفه نامیده می شود.از زمان جنگ جهانی دوم به بعداکثر رویکرد های موجود در زمینه بهینهسازی ،بر روی بهینه سازی تک هدفه متمرکز گشته بود،از همین رو در حال حاضر تکنیکهای بهینه سازی تک هدفه فراوانی مبتنی بر گرادیان نزولی و روشهای جستجوی تصادفی در بهینه سازی تک هدفه موجودمی باشند.
درکنارروشهای جستجوی قطعی،روشهای تصافی جستجو نیز وجود دارند که به الگوریتم های بهینه سازی اجازه یافتن پاسخ بهینه عمومی را با اعتماد بیشتری می دهند.زمانی که یک مساله بیش از یک تابع هدف باشد،یافتن یک یا چند پاسخ بهینه به نام بهینه سازی چند هدفه شناخته می شود. در اصطلاح این دسته از مسائل بهینه سازی به نام مسائل چند ضابطه ای شناخته می شوند. از آنجا که بهینه سازی چند هدفه شامل چندینهدف میباشد،این مساله بدیهی می باشد که بهینه سازی تک هدفه نیز حالت خاصی از بهینه سای چند هدفه می باشد . با این حال دلیل دیگری نیز وجود دارد که چرا درحال حاضر تمرکز بیشتری بر روی مسائل چند هدفه اعمال می شود،مطلبی که در پارگراف بعدی به آن اشاره خواهد شد.
وراحتی های متفاوت وجود دارند که همین امر انتخاب از میان این پاسخها را دشوار می نماید. از همین رو میان هر دو پاسخ مختلف،یک پاسخ از نظر یکی از اهداف نسبت به دیگری دارای برتری می باشد.در خلال دهه گذشته مطالعات گسترده ای به منظور دست یابی به روشهایی برای حل این گونه از مسائل انجام گرفته است. از همین رو روشهای گوناگونی علاوه بر روشهای کلاسیک موجود مطرح گردیده است که از آن جمله روشهای تکراری تصادفی جستجو همانند الگوریتمهای تکاملی و الگوریتم PSO می باشد. در بخش دوم به معرفی بهینه سازی تک/چند خواهد شد و مفاهیم اساسی که در این مباحث وجود ندارد مورد بررسی قرار خواهند گرفت.
معرفی الگوریتم بهینه سازی چند هدفه بر اساس الگوریتم PSOBBO در بهینه سازی چند هدفه و بدست آوردن بهینه ترین پوشش برای شبکه حسگر در بخش پایانی مورد بررسی قرار خواهدگرفت.بسیاری از جستجوهای جهانی حقیقی و مسائل بهینه سازی شامل چندین هدف می باشد.روشهای تک هدفه که در بالا شرح داده شد به طور مستقیم قابلیت اعمال برروی این دست مسائل را ندارند، زیر که ممکن است سبب ایجادمقایسه ای برای انتخاب میان اهداف مختلف گردند. پاسخی که به عنوان یک جواب مناسب برای یک هدف انتخاب می شود ممکن است درقیاس با سایر اهداف مناسب به نظرنرسد.این امر سبب می شود که انتخاب یک پاسخ بهینه تنها در رابطه با یک هدف مناسب به نظر نرسد.
به طور مثال رویه تصمیم گیری درزمان خرید یک اتومبیل را در نظر بگیرید. اتومبیل ها درمحدوده متفاوتی از قیمت ازحدود 1 میلیون تا 300میلیون تومان قرار دارد. اجازه دهید دو پاسخ مرزی را برای سوال در نظر بگیریم . پاسخ ،اتومبیل با قیمت 2 میلیوت تومان است و پاسخ دو ،اتومبیلی با قمیت 200میلیون تومان. بیشینه نمودن تنوع پاسخهای یافت شده به منظور نمایش تعداد اگر هدف ما تنها به قیمت اتومبیل باشد انتخاب میان آنها ساده می باشد، اما زمانی که هد دیگری به نام راحتی اتومبیل به اهداف مساله اضافه می شود،عمل انتخاب به سادگی وجود یک هدف نمی باشد.شکل - 1-1 - نشان دهنده این امر است که ارزانترین اتومیبل دارای راحتی %40 می باشد حال آنکه گرانترین اتومبیل دارای راحتی %90است.
-2 بهینه سازی چند هدفه بر اساس الگوریتم PSO
امروزه نمونه های مختلفی از کار بر روی الگوریتم PSO به منظورحل مسائل بهینه ساز چند هدفه مطرح گردیده است که هر کدام دارای نقاط قوت و ضعف مختلفی می باشند. در این بخش برخی ازمهمترین این روشها مطرح گردیده و مورد سنجش قرار می گیرند. مهمترین هدف الگوریتمهای بهینه سازی چند هدفه یافتن مجموعه ای از پاسخها می باشد که توازنی را میان اهداف مختلف موجود در یک مساله چند هدفه برقرار نمایند. همانطور که پیشتر شرح داده شد،هدف یافتن مجموعه ای از پاسخهای غیر مغلوب می باشد که به نام یک مجموعه پَرِتو انجام می دهند. این عمل شامل سه هدف زیر می باشد: کمینه کردن فاصله میان پاسخهای یافت شدهوجبهه پَرِتو ، بیشترازینقاط متعلق به جبهه پَرِتو،حفظ پاسخهای یافت شده غیر مغلوب. هدف اول به وسیله تعریف یک تابع برازش مناسب به منظور تعیین کیفیت پاسخ یافت شده در مورد اهداف مختلف قابل حصول است. به طور کلی توابع برازش سه نوع مختلف می باشند که عبارتنداز:مبتنی بر مجتمع نمودن ،که در آن تابع برازش به صورت مجموع وزن دار توابع هدف می باشد.
مبتنی بر ضابطه ،که در ن محاسبه برازش در مراحل مختلف بهینه سازی،مابین اهداف مختلف تعویض می شود.مبتنی بر غلبه ،که درآن برازش متناسب است با رتبه بندی پاسخها براساس غلبه .بسیاری از طرحهای مرتب سازی بر اساس غلبه از یک آرشیو از پاسخهای غیر مغلوب یافت شده نیز استفاده می کنند.و برای حصول هدف دوم،روشهایی مطرح گردیده اند تا تنوع موجود درمیان پاسخها را حفظ نمایند .این روشها سبب افزایش احتمال جذب بردارهای تصمیم به نواحازیجبهه پَرِتو می شوند که دارای چگالی کمتری هستند.هدف سوم به وسیله استفادهاز آرشیوی از پاسخهای غیر مغلوب یافت شده محقق می گردد،در واقع از استراتژی نخبه گرایی که در آن بهترین پاسخهای یافت شده در مخزن نگه داری می شوند.
الگوریتم بهینه سازی بر پایهی جغرافیای زیستی - BBO -
مدل های ریاضی از جغرافیای زیستی، مواردی چون کوچ ، انقراض و اسکان گونه های زیستی را شرح می دهند. گونه ها بین جزایر مهاجرت می کنند، واژه ی "جزیره"در اینجا به صورت ترجمه ی توصیفی استفاده شده است نه ترجمه ی تحت لفظی. در واقع جزیره به زیستگاهی گفته می شود که از لحاظ جغرافیایی از مکان های دیگر جدا شده است. تعریف کلاسیک واژه جزیره یعنی اینکه یک جزیره توسط آب از جزایر دیگر جدا شده است. با این همه جزایر می توانند مکان هایی باشند که توسط گستردگی صحرا و رودخانه ها و رشته کوه های صعب العبور، شکارچی ها یا دیگر موانع از هم جدا شده باشند.
جزایری که مکان مناسبی برای گونه های جغرافیایی جهت اسکان باشند گفته می شود که دارای شاخص صلاحیت زیستگاه - HIS - ، بالا هستند. ویژگی هایی که با HSI در ارتباط هستند شامل فاکتورهایی مانند : بارندگی، تنوع گیاهی، ویژگی های نقشه برداری، خاک منطقه و دما می باشند. متغیرهایی که باعث توصیف قابلیت اسکان می شوند متغیر شاخص صلاحیت خوانده می شوند. SIV ها می توانند به عنوان متغیرهای مستقل جزیره و HSI به عنوان متغیر وابسته در نظر گرفته شود. جزایر با HSI بالا، تمایل به داشتن تعداد زیاد گونه ها می باشند در حالی که جزایر با HSI پایین تعداد کمی از گونه ها را در خود جای داده اند. جزایر با HSI بالا دارای گونه های زیادی هستند که به جزایر مجاور مهاجرت می کنند.
مهاجرت به خارج جزایر با HSI بالا، به خاطر تراکم اثرات تصادفی در یک جمعیت بزرگ این چنینی است. برای مثال، مهاجرت به خارج می تواند توسط انتقال موجودات شناور از طریق آب یا از طریق شنا به جزایر مجاور صورت گیرد. جزایر با HSI بالا دارای نرخ مهاجرت به داخل پایینی میباشند چرا که آنها قبلاً توسط گونه های دیگر پر شده اند و نمی توانند پذیرای گونه های جدید باشند. جزایر با HSI پایین به خاطر جمعیت خلوت خود دارای نرخ مهاجرت به داخل بالایی هستند. مهاجرت به داخل گونه های جدید به مکانهایی با HSI پایین ممکن است باعث افزایش HSI آن منطقه شود چرا که مناسب بودن یک مکان متناسب با تنوع جغرافیایی آن است.
کاربرد جغرافیای زیستی برای بهینه سازی برای اولین بار توسط Dan Simon ارائه گردید، که مثالی از این است که چگونه یک فرایند طبیعی می تواند برای بهینه سازی کلی طرح ریزی شود. که این مشابه با همان روندی است که طی چند دهه اخیر برروی مسائلی همچون الگوریتم ژنتیک ، شبکه های عصبی ، بهینه سازی کلونی مورچه ها ، بهینه سازی اجتماع پرندگان و موارد دیگری از هوش محاسباتی صورت گرفته است. جغرافیای زیستی روش طبیعت در توزیع گونه ها می باشد و مشابه با حل مسائل کلی می باشد. فرض کنید ما با تعدادی مساله مواجه هستیم و تعداد معینی از راه حل های کاندیدا داریم، یک راه حل خوب مشابه با یک جزیره با HSI بالا و یک راه حل ضعیف مشابه با HSI پایین می باشد. راه حل ها با HIS بالا بیشتر متمایل به اشتراک ویژگی های خود با راه حل های دیگر و راه حل ها با HSI پایین متمایل به قبول ویژگی های مشترک از راه حل های دیگر هستند.
این دستاورد جدید برای حل مسائل را "بهینه سازی بر پایه ی جغرافیای زیستی" نامیده اند. همانند سایر الگوریتم های تکاملی، هر راه حل ممکن است دارای احتمالی از جهش باشد، با اینکه جهش یک ویژگی اساسی از BBO نمی باشد. BBO ویژگی خاصی در اشتراک با سایر الگوریتم های زیستی مانند GA و PSO دارد. راهحلهای GA درانتهای هر نسل میمیرند، درصورتیکه راهحلهای PSO و BBO برای همیشه زنده میمانند - اگرچه مشخصات آنها درنتیجه پیشرفت فرآیند بهینهسازی تغییر میکند - . راهحلهای PSO خیلی شبیه به خوشهبندی بایکدیگر در گروههای مشابه است، درصورتیکه راهحلهای GA و BBOلزوماً هیچ تمایلی برای خوشه بندی ندارند. شکل 2 یک مدل از فراوانی گونهها در یک زیستگاه را نشان میدهد. نرخ مهاجرت به داخل، ، و نرخ مهاجرت به بیرون، ، توابعی از
