بخشی از متن:
این پاورپوینت در مورد الگوریتم کلونی مورچه ها در 110 اسلاید زیبا شامل:الگوریتم کلونی مورچه ها،الگوریتم مورچه،الگوریتم بهینه سازی مورچه،Ant Colony Optimization Algorithm ،شبکه عصبی،بهینهسازی گروه مورچهها یا ACO ،الگوریتم کلونی مورچه، و... می باشد.
بهینهسازی گروه مورچهها یا ACO همانطور که میدانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز میتوان مطرح کرد. در این روش(ACo)، مورچههای مصنوعی بهوسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانههایی بر روی نمودار، همچون مورچههای واقعی که در مسیر حرکت خود نشانههای باقی میگذارند، باعث میشوند که مورچههای مصنوعی بعدی بتوانند راهحلهای بهتری را برای مسئله فراهم نمایند. همچنین در این روش میتوان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.
300pxاین
روش که از رفتار مورچهها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامه دکترایش مطرح شد.
مقدمه
الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچهها حشراتی اجتماعی هستند که در کلونیها زندگی میکنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچهها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچهها دارای نوعی هوشمندی تودهای است که اخیراً مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچهها ابتدا به طور تصادفی به این سو و آن سو میروند تا غذا بیابند. سپس به لانه بر میگردند و ردّی از فرومون (Pheromone) به جا میگذارند. چنین ردهایی پس از باران به رنگ سفید در میآیند و قابل رویت اند. مورچههای دیگر وقتی این مسیر را مییابند، گاه پرسه زدن را رها کرده و آن را دنبال میکنند. سپس اگر به غذا برسند به خانه بر میگردند و رد دیگری از خود در کنار رد قبل میگذارند؛ و به عبارتی مسیر قبل را تقویت میکنند. فرومون به مرور تبخیر میشود که از سه جهت مفید است:
باعث میشود مسیر جذابیت کمتری برای مورچههای بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راههای کوتاهتر را بیش تر میپیماید و تقویت میکند هر راهی بین خانه و غذا که کوتاهتر (بهتر) باشد بیشتر تقویت میشود و آنکه دورتر است کمتر.
اگر فرومون اصلاً تبخیر نمیشد، مسیرهایی که چند بار طی میشدند، چنان بیش از حد جذّاب میشدند که جستجوی تصادفی برای غذا را بسیار محدود میکردند.
وقتی غذای انتهای یک مسیر جذاب تمام میشد رد باقی میماند.
لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیهٔ مورچهها به احتمال زیادی همان مسیر را دنبال میکنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر، به مرور همهٔ مورچهها هم مسیر میشوند. هدف الگوریتم مورچهها تقلید این رفتار توسط مورچههایی مصنوعی ست که روی نمودار در حال حرکت اند. مسئله یافتن کوتاهترین مسیر است و حلالش این مورچههای مصنوعی اند.
از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دورهگرد است. به طوری که انواع الگوریتم مورچهها برای حل این مسئله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار؛ و لذا با گذر زمان میتواند جواب را به طور زنده تغییر دهد؛ که این خاصیت در روتینگ شبکههای کامپیوتری و سامانه حمل و نقل شهری مهم است.
در مسئله فروشنده دوره گرد باید از یک شهر شروع کرده، به شهرهای دیگر برود و سپس به شهر مبدأ بازگردد بطوریکه از هر شهر فقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)! است که برای فقط ۲۱ شهر زمان واقعاً زیادی میبرد:
روز۱۰۱۳*۷/۱ = S۱۰۱۶*۴۳۳/۲ = ms۱۰*۱۰۱۸*۴۳۳/۲ =!۲۰
با انجام یک الگوریتم برنامه سازی پویا برای این مسئله، زمان از مرتبه نمایی بدست میآید که آن هم مناسب نیست. البته الگوریتمهای دیگری نیز ارائه شده ولی هیچکدام کارایی مناسبی ندارند. ACO الگوریتم کامل و مناسبی برای حل مسئله TSP است.
مسئله فروشنده دوره گرد
مزیتهای ACO
و به مورچهها امکان پیدا کردن کوتاهترین مسیر را میدهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینهسازی میشوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گرهها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گرهای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچهها میتوانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.
کاربردهای ACO
از کاربردهای ACO میتوان به بهینه کردن هر مسئلهای که نیاز به یافتن کوتاهترین مسیر دارد، اشاره نمود:
۱. مسیر یابی داخل شهری و بین شهری.
۲. مسیر یابی بین پستهای شبکههای توزیع برق ولتاژ بالا.
۳. مسیر یابی شبکههای کامپیوتری. ۴-استفاده ازوب. ۵-استفاده ازACOدربهینه سازی شبکههای توزیع آب و…
الگوریتم
پروسهٔ پیدا کردن کوتاهترین مسیر توسط مورچهها، ویژگیهای بسیار جالبی دارد، اول از همه قابلیت تعمیم زیاد و خود- سازمانده بودن آن است. در ضمن هیچ مکانیزم کنترل مرکزی ای وجود ندارد. ویژگی دوم قدرت زیاد آن است. سیستم شامل تعداد زیادی از عواملی است که به تنهایی بیاهمیت هستند بنابراین حتی تلفات یک عامل مهم، تأثیر زیادی روی کارایی سیستم ندارد. سومین ویژگی این است که، پروسه یک فرایند تطبیقی است. از آنجا که رفتار هیچکدام از مورچهها معین نیست و تعدادی از مورچهها همچنان مسیر طولانیتر را انتخاب میکنند، سیستم میتواند خود را با تغییرات محیط منطبق کند و ویژگی آخر اینکه این پروسه قابل توسعه است و میتواند به اندازهٔ دلخواه بزرگ شود. همین ویژگیها الهام بخش طراحی الگوریتمهایی شدهاند که در مسائلی که نیازمند این ویژگیها هستند کاربرد دارند. اولین الگوریتمی که بر این اساس معرفی شد، الگوریتم ABC بود. چند نمونه دیگر از این الگوریتمها عبارتند از: AntNet,ARA,PERA,AntHocNet.
انواع مختلف الگوریتم بهینهسازی مورچگان
در پایین تعدادی از انواع شناخته شده از الگوریتم بهینهسازی مورچگان را معرفی میکنیم:
۱- سیستم مورچه نخبگان: در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد میکند. همچنین این روش برای تمام مورچههای مصنوعی باید انجام شود.
۲- سیستم مورچه ماکسیموم – مینیمم: یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد میکند و تمام گرههای مجاور ان به مقدار فرمون بیشینهمقدار دهی اولیه میشوند.
۳- سیستم کلونی مورچه: که در بالا توضیحات کافی داده شده است.
۴- سیستم مورچه بر اساس رتبه: تمام راه حلهای بدست آماده بر اساس طول جواب رتبهبندی میشوند و بر اساس همین رتبهبندی مقدار فرمون آزاد سازی شده توسط آنها مشخص خواهد شد و راه حل با طول کمتر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد میکند.
۵ - سیستم مورچه متعامد مداوم: در این روش مکانیزم تولید فرمون به مورچه اجازه میدهد تا برای رسیدن به جواب بهتر و مشترک با بقیه مورچهها جستجو انجام دهد با استفاده از روش طراحی متعامد مورچه میتواند در دامنه تعریف شده خود به صورت مداوم برای بدست آوردن بهترین جواب جستجو کند که این عمل به هدف رسیدن به جواب بهینه و صحیح ما را نزدیک میکند. روش طراحی متعامد میتواند به دیگر روشهای جستجو دیگر گسترش پیدا کنند تا به مزیتهای این روشهای جستجو اضافه کند.
بخشی از متن:
تاکنون برای حذف نویزهای آکوستیکی از روش های فعال و غیر فعال استفاده شده است. برخلاف روش غیر فعال میتوان بوسیلهی روش فعال، نویز را در فرکانس های پایین (زیر 500 هرتز)، حذف و یا کاهش داد. در روش فعال از سیستمی استفاده می شود که شامل یک فیلتر وفقی است. به دلیل ردیابی خوب فیلتر LMS در محیط نویزی، الگوریتم FXLMS بعنوان روشی پایه ارائه شده است. اشکال الگوریتم مذکور این است که در مسائل کنترل خطی استفاده می شود. یعنی اگر فرکانس نویز متغیر باشد و یا سیستم کنترلی بصورت غیرخطی کار کند، الگوریتم فوق به خوبی کار نکرده و یا واگرا می شود.
بنابراین در این پایان نامه، ابتدا به ارائه ی گونه ای از الگوریتم FXLMS می پردازیم که قابلیت حذف نویز، با فرکانس متغیر، در یک مجرا و در کوتاهترین زمان ممکن را دارد. برای دستیابی به آن می توان از یک گام حرکت وفقی بهینه ( ) در الگوریتم FXLMS استفاده کرد. به این منظور محدوده ی گام حرکت بهینه در فرکانس های 200 تا 500 هرتز را در داخل یک مجرا محاسبه کرده تا گام حرکت بهینه بر حسب فرکانس ورودی به صورت یک منحنی اسپلاین مدل شود. حال با تخمین فرکانس سیگنال ورودی به صورت یک منحنی اسپلاین مدل شود. حال با تخمین فرکانس سیگنال ورودی بوسیله ی الگوریتم MUSIC ، را از روی منحنی برازش شده، بدست آورده و آن را در الگوریتم FXLMS قرار میدهیم تا همگرایی سیستم در کوتاهترین زمان، ممکن شود. در نهایت خواهیم دید که الگوریتم FXLMS معمولی با گام ثابت با تغییر فرکانس واگرا شده حال آنکه روش ارائه شده در این پایان نامه قابلیت ردگیری نویز با فرکانس متغیر را فراهم می آورد.
همچنینبه دلیلماهیت غیرخطی سیستمهایANC ، به ارائهی نوعی شبکهی عصبی RBF TDNGRBF ) ( میپردازیم که توانایی مدل کردن رفتار غیرخطی را خواهد داشت. سپس از آن در حذف نویز باند باریک فرکانس متغیر در یک مجرا استفاده کرده و نتایج آن را با الگوریتم FXLMS مقایسه می کنیم. خواهیم دید که روش ارائه شده در مقایسه با الگوریتم FXLMS، با وجود عدم نیاز به تخمین مسیر ثانویه، دارای سرعت همگرایی بالاتر (3 برابر) و خطای کمتری (30% کاهش خطا) است. برای حذف فعال نویز به روش TDNGRBF، ابتدا با یک شبکه ی GRBF به شناسایی مجرا میپردازیم. سپس با اعمال N تاخیر زمانی از سیگنال ورودی به N شبکه ی GRBF (با ترکیب خطی در خروجی آنها)، شناسایی سیستم غیرخطی بصورت بر خط امکان پذیر می شود. ضرایب بکار رفته در ترکیب خطی با استفاده از الگوریتم NLMS بهینه می شوند.
فهرست مطالب
عنوان صفحه
چکیده
فصل صفر: مقدمه
1
2
فصل اول: مقدمه ای بر کنترل نویز آکوستیکی 7
1-1) مقدمه 8
1-2) علل نیاز به کنترل نویزهای صوتی (فعال و غیر فعال) 9
1-2-1) بیماری های جسمی 9
1-2-2) بیماری های روانی 9
1-2-3) راندمان و کارایی افراد 9
1-2-4) فرسودگی 9
1-2-5) آسایش و راحتی 9
1-2-6 جنبه های اقتصادی 10
1-3) نقاط ضعف کنترل نویز به روش غیرفعال 10
1-3-1) کارایی کم در فرکانس های پایین 10
1-3-2) حجم زیاد عایق های صوتی 10
1-3-3) گران بودن عایق های صوتی 10
1-3-4) محدودیت های اجرایی 10
1-3-5) محدودیت های مکانیکی 10
1-4) نقاط قوت کنترل نویز به روش فعال 11
1-4-1) قابلیت حذف نویز در یک گسترده ی فرکانسی وسیع 11
1-4-2) قابلیت خود تنظیمی سیستم 11
1-5) کاربرد ANC در گوشی فعال 11
1-5-1) تضعیف صدا به روش غیر فعال در هدفون 12
1-5-2) تضعیف صدا به روش آنالوگ در هدفون 13
1-5-3) تضعیف صوت به روش دیجیتال در هدفون 15
1-5-4) تضعیف صوت به وسیله ی ترکیب سیستم های آنالوگ و دیجیتال در هدفون 16
1-6) نتیجه گیری 17
فصل دوم: اصول فیلترهای وفقی
18
2-1) مقدمه 19
2-2) فیلتر وفقی 20
2-2-1) محیط های کاربردی فیلترهای وفقی 22
2-3) الگوریتم های وفقی 25
2-4) روش تحلیلی 25
2-4-1) تابع عملکرد سیستم وفقی 26
2-4-2) گرادیان یا مقادیر بهینه بردار وزن 28
2-4-3) مفهوم بردارها و مقادیر مشخصه R روی سطح عملکرد خطا 30
2-4-4) شرط همگرا شدن به٭ W 32
2-5) روش جستجو 32
2-5-1) الگوریتم جستجوی گردایان 32
2-5-2) پایداری و نرخ همگرایی الگوریتم 35
2-5-3) منحنی یادگیری 36
2-6) MSE اضافی 36
2-7) عدم تنظیم 37
2-8) ثابت زمانی 37
2-9) الگوریتم LMS 38
2-9-1) همگرایی الگوریتم LMS 39
2-10) الگوریتم های LMS اصلاح شده 40
2-10-1) الگوریتم LMS نرمالیزه شده (NLMS) 41
2-10-2) الگوریتم های وو LMS علامتدار وو (SLMS) 41
2-11) نتیجه گیری 43
فصل سوم: اصول کنترل فعال نویز
44
3-1) مقدمه 45
3-2) انواع سیستم های کنترل نویز آکوستیکی 45
3-3) معرفی سیستم حذف فعال نویز تک کاناله 47
3-4) کنترل فعال نویز به روش پیشخور 48
3-4-1) سیستم ANC پیشخور باند پهن تک کاناله 49
3-4-2) سیستم ANC پیشخور باند باریک تک کاناله 50
3-5) سیستم های ANC پسخوردار تک کاناله 51
3-6) سیستم های ANC چند کاناله 52
3-7) الگوریتم هایی برای سیستم های ANC پسخوردار باند پهن 53
3-7-1) اثرات مسیر ثانویه 54
3-7-2) الگوریتم FXLMS 57
3-7-3) اثرات فیدبک آکوستیکی 61
3-7-4) الگوریتم Filtered- URLMS 66
3-8) الگوریتم های سیستم ANC پسخوردار تک کاناله 69
3-9) نکاتی درباره ی طراحی سیستم های ANC تک کاناله 70
3-9-1) نرخ نمونه برداری و درجه ی فیلتر 72
3-9-2) علیت سیستم 73
3-10) نتیجه گیری 74
فصل چهارم: شبیه سازی سیستم ANC تک کاناله
75
4-1) مقدمه 76
4-2) اجرای الگوریتم FXLMS 76
4-2-1) حذف نویز باند باریک فرکانس ثابت 76
4-2-2) حذف نویز باند باریک فرکانس متغیر 81
4-3) اجرای الگوریتم FBFXLMS 83
4-4) نتیجه گیری 85
فصل پنجم: کنترل غیرخطی نویز آکوستیکی در یک ماجرا
86
5-1) مقدمه 87
5-2) شبکه عصبی RBF 88
5-2-1) الگوریتم آموزشی در شبکه ی عصبی RBF 90
5-2-2) شبکه عصبی GRBF 93
5-3) شبکه ی TDNGRBF 94
5-4) استفاده از شبکه ی TDNGRBF در حذف فعال نویز 95
5-5) نتیجه گیری 98
فصل ششم: نتیجه گیری و پیشنهادات
99
6-1) نتیجه گیری 100
6-2) پیشنهادات 101
مراجع I