الگوریتم ها

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
... در این تاپیک درمورد الگوریتم های مختلف در متلب بحث می شود ...

.... تمامی مطالبی که در این تاپیک قرار گرفته اند از سایت http://mathworks.ir می باشند ....


:gol:
:gol::gol:

 
آخرین ویرایش:

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
الگوریتم کلونی مورچه ها Ant Colony Optimization

الگوریتم کلونی مورچه ها Ant Colony Optimization

انسان هميشه براي الهام گرفتن به جهان زنده پيرامون خود نگريسته است. يکي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوينچي(1519-1452) طرحي از يک ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشين پرنده اي ساخت که داراي موتور بود و بجاي بال از ملخ استفاده مي کرد.
هم اکنون کار روي توسعه سيستم هاي هوشمند با الهام از طبيعت از زمينه هاي خيلي پرطرفدار هوش مصنوعي است. الگوريتمهاي ژنتيک که با استفاده از ايده تکاملي دارويني و انتخاب طبيعي مطرح شده، روش بسيار خوبي براي يافتن مسائل بهينه سازيست. ايده تکاملي دارويني بيانگر اين مطلب است که هر نسل نسبت به نسل قبل داراي تکامل است و آنچه در طبيعت رخ مي دهد حاصل ميليون ها سال تکامل نسل به نسل موجوداتي مثل مورچه است.

الگوريتم کلوني مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد.

عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

الگوريتم کلوني مورچه الهام گرفته شده از مطالعات و مشاهدات روي کلوني مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلوني ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلوني است تا درجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلوني) و هوشمندي اجتماعي را روشن کنيم.

در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال در فرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نه مثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازم براي فرد معمار با يک کارگر ساده متفاوت است.

در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازيست.

جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم :

فرآيند ساخت لانه توسط موريانه ها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سه فعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرف و آن طرف حرکت مي کنند. هر موريانه به محض رسيدن به فضايي که کمي بالاتر از سطح زمين قرار دارد شروع به ترشح بزاق مي کنند و خاک را به بزاق خود آغشته مي کنند. به اين ترتيب گلوله هاي کوچک خاکي با بزاق خود درست مي کنند. عليرغم خصلت کاملا تصادفي اين رفتار، نتيجه تا حدي منظم است. در پايان اين مرحله در منطقه اي محدود تپه هاي بسيار کوچک مينياتوري از اين گلوله هاي خاکي آغشته به بزاق شکل مي گيرد. پس از اين، همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه براي موريانه ها عمل مي کنند. هر موريانه به محض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاکي با بزاق خود مي کند. اين کار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني که ارتفاع هر ستون به حد معيني برسد. در اين صورت موريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديکي ستون فعلي ستون ديگيري نباشد بلافاصله آن ستون را رها مي کنند در غير اين صورت يعني در حالتي که در نزديکي اين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل کردن ستونها و ساختن لانه مي کنند.

تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده اي موريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا بر اساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه ها کاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران سختماني مستقيم و از طريق کلمات و ... است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنها از طريق تغييرات ايجاد شده در محيط ممکن مي سازد.
بهينه سازي مسائل بروش کلوني مورچه(ACO)
همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

روز1013*7/1 = S1016*433/2 = ms10*1018*433/2 = !20

با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.


مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي( Statistical) مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري قبلا از آن عبور کرده باشند. حال دقت کنيد که همين يک تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA مي آيد و بهC مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.

نکه بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.


مزيتهاي ACO

همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.



کاربردهاي ACO

از کاربردهاي ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :
1. مسير يابي داخل شهري و بين شهري

2. مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا

3. مسير يابي شبکه هاي کامپيوتري



مسير يابي شبکه هاي کامپيوتري با استفاده از ACO

در ابتدا مقدمه اي از نحوه مسير يابي در شبکه هاي کامپيوتري را توضيح خواهيم داد :

اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.

روشي بنام ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلوني مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

منبع:
http://www.e-commerc.blogfa.com
 

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
حل مساله TSP با استفاده از الگوریتم ترکیبی جهش قورباغه

حل مساله TSP با استفاده از الگوریتم ترکیبی جهش قورباغه

الگوریتم ترکیبی جهش قورباغه (SFLA)یک الگوریتم ممتیک متاهیوریستیک جدید است که توابع ریاضی کارا و قابلیت جستجوی سراسری را دارد. مساله فروشنده­ی دوره­گرد (TSP)یک مساله­ی بهینه­سازیِ ترکیبیِ پیچیده است که به عنوان محکی برای ارزیابیِ سودبخشی و کاراییِ الگوریتم­های بهینه­سازی که به تازگی پیشنهادشده­اند، استفاده می­شود. زمانیکه از الگوریتم ترکیبی جهش قورباغه برای حل TSP استفاده می­شود، memeplex و submemeplex ساخته می­شوند و روند الگوریتم، به ویژه جستجوی محلی در submemeplex به دقت مطابق SFLAِ اصلی می­شود. نتایج تجربی نشان می­دهند که الگوریتم ترکیبیِ جهش قورباغه برای حل مسائل TSP ای که مقیاس کوچکی دارند کارا است. به ویژه در TSP ای که 51 شهر دارد، الگوریتم موفق می­شود 6 مسیر که کوتاهتر از مسیر بهینه­ی ایجاد شده توسط TSPLIB هستند را بیابد. طول کوتاهترین مسیر به جای اینکه برابر با 429.98 که در سایر مراجع ذکر شده باشد ، برابر 428.87 است.مساله­ی معروف فروشنده­ی دوره­­گرد (TSP) یک مساله­ی بهینه­سازیِ ترکیبی متداول است که معمولاً جهت ارزیابی کارایی الگوریتم­های متاهیوریستیک بکارگرفته می­شود. در حال حاضر الگوریتم­های متاهیوریستیک عمدتاً شامل الگوریتم ژنتیک (GA)، الگوریتم بهینه­سازیِ کلونی مورچه­ها (ACO) و الگوریتم بهینه­سازی گروه ذرات (PSO) می­باشند. هر یک از این الگوریتم­های متاهیوریستیک توانایی­ها و ضعف­هایی برای حل مساله­ی TSP دارند. برای مثالGA ممکن است زمان بسیار زیادی را برای جستجوی پاسخ بهینه صرف کند ، درصورتیکه ACO کلاً تعدادی پارامتر دارد و زمان کمتری صرف می­کند. اما ACO به آسانی در بهینه­ی محلی می­افتد. PSO نسبتاً ساده است و توجه پژوهشگران را در زمینه­های مختلف جلب کرده است. اخیراً دو پژوهشگر به نام­های Muzaffar Eusuff و Kevin Lansey از طریق مشاهده­، تقلید و مدلسازیِ رفتار قورباغه­ها که غذاهای موجود بر روی سنگ­های مجزایی که به صورت تصادفی در تالاب قرارگرفته­اند را جستجو می کنند، یک الگوریتم متاهیوریستک جدید با نام الگوریتم ترکیبی جهش قورباغه (SFLA) ایجاد کردند.
SFLA : Shuffled frog-leaping algorithm
TSP : Traveling Salesman Problem
GA : Genetic Algorithm
ACO : Ant Colony Optimization
PSA :particle Swarm Algorithm
 

پیوست ها

  • SFLA_TSP(mathworks.ir).pdf
    1 مگایابت · بازدیدها: 0

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
الگوریتم زنبور عسل

الگوریتم زنبور عسل

الگوریتم زنبور شامل گروهی مبتنی بر الگوریتم جستجو است که اولین بار در سال 2005 توسعه یافت ؛ این الگوریتم شبیه سازی رفتار جستجوی غذای گروههای زنبور عسل است. در نسخه ابتدایی این الگوریتم، الگوریتم نوعی از جستجوی محلی انجام می دهد که با جستجوی کتره ای (Random) ترکیب شده و می تواند برای بهینه سازی ترکیبی {زمانی که بخواهیم چند متغیر را همزمان بهینه کنیم.}یا بهینه سازی تابعی به کار رود.

جستجوی غذا در طبیعت

یک کلونی زنبور عسل می تواند در مسافت زیادی و نیز در جهت های گوناگون پخش شود تا از منابع غذایی بهره برداری کند.
قطعات گلدار با مقادیر زیادی نکتار و گرده که با تلاشی کم قابل جمع آوری است،به وسیلهی تعداد زیادی زنبور بازدید می شود؛ به طوری که قطعاتی از زمین که گرده یا نکتار کمتری دارد، تعداد کمتری زنبور را جلب می کند.
پروسه ی جستجوی غذای یک کلونی به وسیله ی زنبورهای دیده بان آغاز می شود که برای جستجوی گلزار های امید بخش (دارای امید بالا برای وجود نکتار یا گرده) فرستاده می شوند.
زنبورهای دیده بان به صورت کتره ای(Random) از گلزاری به گلزار دیگر حرکت می کنند.
در طول فصل برداشت محصول (گل دهی)، کلونی با آماده نگه داشتن تعدادی از جمعیت کلونی به عنوان زنبور دیده بان به جستجوی خود ادامه می دهند. هنگامی که جستجوی تمام گلزار ها پایان یافت، هر زنبور دیده بان ، بالای گلزاری که اندوخته ی کیفی مطمئنی از نکتار و گرده دارد، رقص خاصی را اجرا می کند.

این رقص که به نام "رقص چرخشی"(حرکتی مانند حرکت قرقره) شناخته می شود، اطلاعات مربوط به جهت تکه گلزار(نسبت به کندو)، فاصله تا گلزار و کیفیت گلزار را به زنبور های دیگر انتقال می دهد. این اطلاعات زنبور های اضافی و پیرو را به سوی گلزار می فرستد.
بیشتر زنبور های پیرو به سوی گلزار هایی میروند که امید بخش تر هستند و امید بیشتری برای یافتن نکتار و گرده در آنها، وجود دارد.

وقتی همه ی زنبور ها به سمت ناحیه ای مشابه بروند، دوباره به صورت کتره ای (Random) و به علت محدوده ی رقصشان در پیرامون گلزار پراکنده می شوند تا به موجب این کار سرانجام نه یک گلزار ، بلکه بهترین گل های موجود درون آن تعیین موقعیت شوند.

الگوریتم

الگوریتم زنبور هر نقطه را در فضای پارامتری_ متشکل از پاسخ های ممکن_به عنوان منبع غذا تحت بررسی قرار می دهد."زنبور های دیده بان"_ کارگزاران شبیه سازی شده _به صورت کتره ای (Random) فضای پاسخ ها را ساده می کنند و به وسیله ی تابع شایستگی کیفیت موقعیت های بازدید شده را گزار ش می دهند. جواب های ساده شده رتبه بندی می شوند، و دیگر "زنبورها" نیروهای تازه ای هستند که فضای پاسخ ها را در پیرامون خود برای یافتن بالا ترین رتبه محل ها جستجو می کنند(که "گلزار" نامیده می شود) الگوریتم به صورت گزینشی دیگر گلزار ها را برای یافتن نقطه ی بیشینه ی تابع شایستگی جستجو می کند.

کاربرد ها

برخی کاربرد های الگوریتم زنبور در مهندسی:
آموزش شبکه عصبی برای الگو شناسی
زمان بندی کارها برای ماشین های تولیدی
دسته بندی اطلاعات
بهینه سازی طراحی اجزای مکانیکی
بهینه سازی چند گانه
میزان کردن کنترل کننده های منطق فازی برای ربات های ورزشکار

توضیات بیشتر در:
صفحه الگوریتم زنبور عسل در ویکیپدیای انگلیسی
 

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
هوش جمعی (Swarm Intelligence)

هوش جمعی (Swarm Intelligence)

هوش جمعی (Swarm Intelligence) نوعی روش هوش مصنوعی است که مبتنی بر رفتارهای جمعی در سامانه‌های نامتمرکز و خودسامانده بنیان شده است. این سامانه‌ها معمولاً از جمعیتی از کنشگران ساده تشکیل شده است که بطور محلی با یکدیگر و با محیط خود در تعامل هستند. با وجود اینکه معمولاً هیچ کنترل تمرکزیافته‌ای، چگونگی رفتار کنش‌گران را به آنها تحمیل نمی‌کند، تعاملات محلی آنها به پیدایش رفتاری عمومی می‌انجامد. مثال‌هایی از چنین سیستم‌های را می‌توان در طبیعت مشاهده کرد؛ گروه‌های مورچه‌ها، دستهٔ پرندگان، گله‌های حیوانات، تجمعات باکتری‌ها و دسته‌های ماهی‌ها.


روباتیک ازدحامی، کاربردی از اصول هوش مصنوعی ازدحامی در تعداد زیادی از روبات‌های ارزان قیمت است.
روش‌های هوش ازدحامی
از موارد روش‌های فرااکتشافی می‌توان به موارد زیر اشاره کرد
• روش بهینه‌سازی گروه مورچه‌ها یا ACO
• الگوریتم کوچ پرستوها یا روش بهینه‌سازی ازدحام ذرات PSO
• روش شبیه‌سازی کوره‌ای
• روش جستجوی مبتنی بر منع
• روش محاسبات تکاملی
دو روش اول موفق‌ترین روش‌های هوش مصنوعی ازدحامی که تاکنون وجود دارند.
الگوریتم مورچه‌ها
روش ACO، نوعی روش فرااکتشافی است که برای یافتن راه‌حل‌های تقریبی برای مسائل بهینه‌سازی ترکیبیاتی مناسب است. روش ACO، مورچه‌های مصنوعی به‌وسیله‌ٔ حرکت بر روی گرافِ مساله و با باقی گذاشتن نشانه‌هایی بر روی گراف، همچون مورچه‌های واقعی که در مسیر حرکت خود نشانه‌های باقی می‌گذارند، باعث می‌شوند که مورچه‌های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مساله فراهم نمایند.
الگوریتم کوچ پرستوها
روش PSO یک روش سراسری کمینه‌سازی است که با استفاده از آن می‌توان با مسائلی که جواب آنها یک نقطه یا سطح در فضای n بعدی می‌باشد، برخورد نمود. در اینچنین فضایی، فرضیاتی مطرح می‌شود و یک سرعت ابتدایی به آنها اختصاص داده می‌شود، همچنین کانال‌های ارتباطی بین ذرات درنظر گرفته می‌شود. سپس این ذرات در فضای پاسخ حرکت می‌کنند، و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازه‌ٔ زمانی محاسبه می‌شود. با گذشت زمان، ذرات به سمت ذراتی که دارای ملاک شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب می‌گیرند. مزیت اصلی این روش بر استراتژی‌های کمینه‌سازی دیگر این است که، تعداد فراوان ذرات ازدحام کننده، باعث انعطاف روش در برابر مشکل پاسخ کمینه‌ٔ محلی می‌گردد.
جذابیت هوش ازدحامی در فناوری اطلاعات
همگونی‌هایی بین مسائل متفاوت در حوزهٔ فناوری اطلاعات و رفتارهای حشرات اجتماعی وجود دارد :
• سامانه‌ای توزیع‌شده از کنشگرهای مستقل و تعامل‌کننده.
• اهداف: بهینه‌سازی کارآیی و توان.
• خودتنظیم‌بودن در روش‌های کنترل و همکاری به شکل نامتمرکز.
• توزیع کار و اختصاص وظایف به شکل توزیع‌شده.
• تعاملات غیرمستقیم.
مراحل طراحی یک سامانه
مراحل طراحی یک سامانه با کاربردهای فناوری اطلاعات بر مبنای هوش مصنوعی ازدحامی فرآیندی سه مرحله‌ای است :
• شناسایی همسانی‌ها: در سامانه‌های IT و طبیعت.
• فهم: مدلسازی رایانه‌ای روش ازدحامی طبیعی به شکل واقع‌گرا.
• مهندسی: ساده‌سازی مدل و تنظیم آن برای کاربردهای IT.
کاربردهای فعلی و آتی
• مسیریابی در شبکه.
• سامانه‌های توزیع‌شده‌ٔ رایانه‌ای.
• اختصاص منابع به شکل بهینه.
• زمان‌بندی وظایف.
• بهینه‌سازی ترکیبیاتی.
• روباتیک:
o بررسی سیستم‌های لوله‌کشی.
o تعمیرات و نگهداری ماهواره‌ها و کشتی‌ها.
o روبات‌های خود-مونتاژ.
منابع
Swarm Intelligence. در دانشنامهٔ ویکی‌پدیا انگلیسی.
 

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
الگوریتم ژنتیک

الگوریتم ژنتیک

حساب تکاملي ,براي اولين بار در سال 1960 توسط آقاي ريچنبرگ ارائه شد که تحقيق وي در مورد استراتژي تکامل بود.بعدها نظريه او توسط محققان زيادي مورد بررسي قرار گرفت تا اينکه الگوريتم ژنتيک (GA ) توسط جان هولند(John Holland ) و در سال 1975 در دانشگاه ميشيگان ,ارائه شد.
در سال 1992 نيز جان کوزا (John Koza ) از الگوريتم ژنتيک (GA ) براي حل و بهينه سازي مسائل مهندسي پيشرفته استفاده کرد و توانست براي اولين بار روند الگوريتم ژنتيک (GA ) را به زبان کامپيوتر در آورد و براي آن يک زبان برنامه نويسي ابداع کندکه به اين روش برنامه نويسي ,برنامه نويسي ژنتيک (GP ) گويندو نرم افزاري که توسط وي ابداع گرديد به نرم افزار LISP مشهور است که هم اکنون نيز اين نرم افزار کاربرد زيادي در حل و بهينه سازي مسائل مهندسي پيدا کرده است .


در الگوريتم‏هاي ژنتيكي, در طي مرحله توليد مثل ازعملگرهاي ژنتيكي استفاده مي‏شود. با تاثير اين عملگرها بر روي يك جمعيت, نسل بعدي آن جمعيت توليد مي‏شود. عملگرهاي انتخاب , آميزش و جهش معمولاً بيشترين كاربرد را درالگوريتم‏هاي ژنتيكي دارند.

برخي از كاربرد الگوريتم‏هاي ژنتيكي


توپولوژي هاي شبکه هاي کامپيوتي توزيع شده.
بهينه سازي ساختار ملکولي شِميايي (شيمي)
مهندسي برق براي ساخت آنتنهاي Crooked-Wire Genetic Antenna
مهندسي نرم افزار
بازي هاي کامپيوتري
مهندسي مواد
مهندسي سيستم
رباتيک(Robotics)
تشخيص الگوو استخراج داده(Data mining)
حل مسئله فروشنده دوره گرد
آموزش شبکه هاي عصبي مصنوعي
ياددهي رفتار به رباتها با GA .
يادگيري قوانين فازي با استفاده از الگويتم هاي ژنتيک.
 

پیوست ها

  • GA.pdf
    348.5 کیلوبایت · بازدیدها: 0

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
CLA-PSO: يک مدل ترکیبی براي بهينه سازي

CLA-PSO: يک مدل ترکیبی براي بهينه سازي

در اين مقاله یک مدل جديد که از تركيب اتوماتاي يادگير سلولي و مدل حركت دسته جمعي ذرات حاصل میشود برای بهینه سازی پیشنهاد میگردد. در مدل پیشنهادی در هر سلول از اتوماتاي يادگيرسلولي يك جمعيت از ذرات قرار داده میشود. اتوماتای يادگير در هر سلول وظيفه تنظيم رفتار ذرات جمعيت ان سلول و برقراري موازنه بين فرایند جستجوي سراسري و جستجوي محلي را بر عهده دارد. براي انجام اين وظيفه، اتوماتای يادگير موجود در هر سلول از تجربيات خود و اتوماتاي يادگير سلولهاي همسايه بهره ميبرد. نتايج آزمايشها بر روي مسايل نمونه نشان ميدهد كه روش ارائه شده از عملكرد بهتري در مقایسه با مدل PSO استاندارد برخوردار است.
حرکت جمعي ذرات(PSO)، يک تکنيک بهينه سازي احتمالي است که بر مبناي جمعيت کار ميکند. اين روش در سال 1995 توسط دکتر ابرهارت و دکتر کندي ارائه شد و ايده اصلي آن از رفتار دسته جمعي ماهيها يا پرندگان به هنگام جستجوي غذا الهام گرفته شده است. گروهي از پرندگان در فضايي به صورت تصادفي دنبال غذا ميگردند. تنها يک تکه غذا در فضاي مورد بحث وجود دارد. هيچ يک از پرندگان محل غذا را نميدانند. يکي از بهترين استراتژيها ميتواند دنبال کردن پرنده اي باشد که کمترين فاصله را تا غذا داشته باشد. اين استراتژي در واقع جانمايه الگوريتم PSO است. در الگوريتم PSO، هر راه حل که به آن يک ذره گفته ميشود، معادل يک پرنده در الگوري حرکت جمعي پرندگان ميباشد. هر ذره يک مقدار شايستگي دارد که توسط يک تابع شايستگي محاسبه ميشود. هر چه ذره در فضاي جستجو به هدف- غذا در مدل حرکت پرندگان- نزدکتر باشد، شايستگي بيشتري دارد.. همچنين هر ذره داراي يک سرعت است که هدايت حرکت ذره را بر عهده دارد. هر ذره با دنبال کردن ذرات بهينه در حالت فعلي، به حرکت خود در فضاي مساله ادامه ميدهد. اتوماتاي سلولي يک مدل رياضي براي سيستمهايي است که در آنها چندين مؤلفه ساده براي توليد الگوهاي پيچيده با هم همکاري مي­کنند. در اتوماتاي سلولي يک مجموعه منظم از سلولها وجود دارد که هر کدام مي­توانند با چند مقدار مختلف که تعدادشان متناهي است، مقداردهي شوند. اين سلولها به صورت همگام و در زمانهاي گسسته بر طبق يک قانون محلي بهنگام­رساني مي­شوند. محلي بودن به اين معناست که در تعيين مقدار جديد هر سلول، سلولهايي که در همسايگي وي هستند تاثيرگذار هستند و سلولهاي دورتر، تاثيري ندارند. شبکه سلولها مي­تواند ابعاد متفاوتي داشته باشند و يک­, دو و يا بيشتر بعد داشته باشند.ويژگيهاي اتوماتاي سلولي را به اختصار ميتوان به صورت زير بيان نمود: فضا و زمان به صورت گسسته پيش ميروند. اتوماتا همگن است. عمل به روزرساني به صورت همگام انجام ميشود و قوانين بر اساس همسايه هاي هر سلول تعريف ميشوند. از مشکلات مهم اتوماتاي سلولي تعيين فرم قطعي قوانين است. زيرا در اغلب سيستمها نويز و عدم قطعيت وجود دارند كه سيستم را تحت تاثير قرار ميدهند. لذا تعيين فرم قطعي قوانين در اين سيستمها کاري مشكل و در برخي موارد غير ممكن است.
 

پیوست ها

  • CSI-CLAPSO.pdf
    566.5 کیلوبایت · بازدیدها: 0

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
رمزنگاري كليد عمومي وrsa

رمزنگاري كليد عمومي وrsa

مروري كوتاه:
رمزنگاري كليد مخفي: رمزنگاري سنتي كليد مخفي؛ از يك كليد تنها كه بين هر دو طرف گيرنده و فرستنده به اشتراك گذاشته شده است استفاده مي كند.اگر اين كليد فاش شود ارتباط به خطر مي افتد.همچنين اين روش از گيرنده در برابر پيام هاي جعلي ارسال شده كه ادامي كنند از طرف فرستنده ي خاصي مي ايند محافظت نمي كند.
رمزنگاري كليد عمومي: اين روش كه رمزنگاري دوكليده نيز خوانده مي شود از دو كليد براي عمل رمز نگاري استفاده مي كند:
يكي كليد عمومي كه توسط همه شناخته شده است.و براي به رمز درآوردن پيغام ها و تشخيص امضا ها مورد استفاده قرار مي گيرد.
ديگري كليد خصوصي كه فقط گيرنده از آن اطلاع دارد و براي رمز گشايي پيغام و همچنين ايجاد امضا مورد استفاده قرار مي گيرد.

اشكال سيستمهاي كليد مخفي:
يك از اشكال هاي الگوريتم هاي بر پايه كليد متقارن اين است كه شما نياز به يك روش مطمئن براي انتقال كليد هاي طرفين داريد.به اين مفهوم كه يا از يك كانال امن اين كار را انجام دهند يا به منظور انتقال كليد همديگر را ملاقات كنند.اين ميتواند يك مشكل بزرگ باشد
و قطعا كارآساني نيست.اشكال ديگر اين روش اين است كه شما براي ارتباط با هر شخصي كليدي جداگانه نياز داريد.



سناريوي ارتباط:
آليس وباب مي خواهند با هم مكالمه مطمئني داشته باشند طوري كه كس ديگري از اطلاعات مبادله شده در اين مكالمه با خبر نشود.درهمين زمان Eve در حال استراق سمع است.
آليس و باب ميتوانند خلبان دو جت نظامي يا دو تاجر اينترتي يا فقط دو دوست باشند كه مي خواهند با هم يك مكالمه ي خصوصي داشته باشند.آنها نمي توانند Eve را از گوش دادن به سيگنال راديوي يا اطلاعات مبادله شده از طريق تلفن و .. باز دارند.پس چه كاري مي توانند انجام دهند تا اين ارتباط مخفي بماند؟
رمزنگاري كليد خصوصي:
يك راه حل اين است كه آليس و باب يك كليد دجيتالي را مبادله كنند.بعد وقتي هر دو از آن كليد آگاه شدند(ولي ديگران از آن بيخبرند).آليس از اين كليد استفاده مي كند تا پيغام ها را به رمز كرده و به باب بفرستد.باب نيز پيغام اوليه را با استفاده از اين كليد و رمزگشايي پيغام بازسازي مي كند.پيغام رمز شده براي Eve قابل استفاده نيست .او كليد را نميداند پس نمي تواند پيغام اصلي را باز يابي كند.با يك الگوريتم رمزنگاري خوب اين طرح قابل اجراست. ولي مبادله كليد به طوري كه اين كليد از Eve مخفي بماند يك معضل است.اين كار واقعا نياز به يك ارتباط رودرو دارد كه هميشه امكان پذير نيست.
رمز نگاري كليد عمومي: اين رمزنگاري به صورت متفاوتي عمل مي كند.زيرا كليد را به دو قسمت كليد عمومي براي به رمز در آوردن و كليد خصوصي براي رمزگشايي تقسيم مي كند.اين ممكن نيست كه كليد خصوصي از كليد عمومي قابل تعيين باشد.همان طور كه در شكل مي بينيد؛باب يك جفت كليد توليد مي كند.يكي از كليدها كليد عمومي است كه بايد به اطلاع عموم (از جمله Eve) برسد. و ديگري كليد خصوصي كه فقط خود باب از آن اطلاع دارد.هر كسي مي تواند از كليد عمومي باب براي ارسال پيغام به او استفاده كنند.ولي فقط باب مي تواند.از كليد خصوصي خودش براي رمز گشايي پيغام ها استقاده كند.اين طرح به آليس و باب اجازه مي دهد تا يك ارتباط امن را بدون ملاقات كردن هم داشته باشند.
هر چند اگر Eve بتواند به همان راحتي كه مي تواند به پيغام هاي مبادله شده بين باب و آليس گوش مي دهد آنها را دست كاري نيز كند؛ مي تواند كليد عمومي خود را جانشين كليد عمومي باب كند و سپس آليس از كليد عمومي او براي رمز كردن پيغام ها و فرستادن آنها استفاده مي كند.
Man in middle attack : (حمله ي پل زدن به سطل)
اين حمله براي ارتباطات رمز شده و پرتوكل هاي مبادله ي كليد مناسب است.ايده ي اين حمله اين است كه وقتي دو طرف در حال مبادله ي كليد هاي عمومي شان هستند مهاجم خودش را در بين دو طرف در خط ارتباط قرار مي دهد.سپس به مبادله كليد به صورت جداگانه با هر كدام از طرفين مي پردازد.سپس هر كدام از طرفين كليد عمومي خودش را به طرف ديگر مي دهد(كه البته هيچ گاه به دست طرف مقابل نمي رسد و در واقع هر كدام از اين دو در حال مبادله ي كليد با مهاجم هستند)مهاجم براي هر كدام از طرفين طرف دوم ارتباط امن را تشكيل مي دهد.سپس مهاجم براي هر كدام از اين دو ارتباط امن از كليد مناسبش استفاده مي كند.طرفين تصور مي كنند كه مكالمه امن ي انجام مي دهند ولي در حقيقت مهاجم همه چيز را شنيده است.
پرهيز ازحمله ي پل زدن به سطل:
روش معمول براي جلوگيري از حمله ي پل زدن به سطل اين است كه؛ از يك الگوريتم رمز گذاري كليد عمومي استفاده كنيم كه قابليت امضاي ديجيتالي را داشته باشد.براي برپايي چنين سيستمي طرفين بايد كليد عمومي ديگري را از قبل بداند(كه اين از مزيت اصلي رمز گذاري كليد عمومي مي كاهد. ) پس از توليد كليد خصوصي توليد شده طرفين امضاي ديجيتالي خود را براي هم مي فرستند.مهاجم كه خود را در وسط قرار داده ممكن است بتواند تا اين جاي ارتباط را گوش دهد ولي ديگر قادر نخواهد بود كه امضاي ديجيتالي را جعل كند. زيرا امضا ي ديجيتالي قابل جعل نيست.
منتشر كردن كليد عمومي:
فهرست كليد هاي عمومي براي اين ايجاد شد تا مشكل اين كه هر كاربر مي بايست يك كپي از كليد عمومي تمام اشخاص را داشته باشد تا با آنها ارتباط امن بر قرار كند را بر طرف كند.هر كاربري كليد عمومي خود را در فهرست ثبت ميكند و وقتي مثلا A خواست تا به B يك پيغام رمز شده بفرستد او كليد عمومي B را از طريق فرستادن درخواست KUB به فهرست انجام مي دهد.
مشكلات كليد ها:
· ما ممكن است كليد خود را گم كنيم.
· ما ممكن است فراموش كنيم كدام كليد براي چه كاري بود،
· ما ممكن است يك كليد را به شخص اشتباهي بدهيم.
· يك كسي ممكن است كليد ما را بدزدد.
· يك كسي ممكن است از طريق پنجره وارد شود.
· كسي ممكن است در را بشكند.
· كسي ممكن است درخواست ورود به خانه را بكند و يك احمق هم به او اين اجازه را بدهد.
· كسي ممكن است بتواند موفق به دريافت گواهيي شود كه به او اجازه انجام كار هايي فرا تر از آنجه لازم است را بدهد.
· كسي ممكن است خانه را به آتش بكشاند و اغتشاش ايجاد كند.

الگوريتم هاي كليد عمومي:
الگوريتم هاي كليد عمومي از يك جفت كليد عمومي و خصوصي بر روي يك پيغام استفاده مي كنند.
· فقط كليد خصوصي مي تواند پيغام رمز شده با كليد كليد عمومي را رمزگشايي كند.
· همچنين فقط كليد عمومي قادر خواهد بود پيغام رمز شده با كليد خصوصي را رمز گشايي كند.
· اگر شما باكليد عمومي من پيغامي را رمز كنيد. فقط من قادر به خواندن آن پيغام خواهم بود.
· اگر شما بتوانيد پيغامي را با كليد عمومي من باز كنيد آن پيغام الزاما از طرف من آمده است.
· اين طرح اولين بار توسط وايتفيلد ديفه و مارتين هلمن و به صورت مستقلانه اي در همين زمان يعني دهه ي 70 توسط رالف مركل پيشنهاد گرديد.
· سازمان NSA (سازماني سري در امريكا كه روي مباحث رمزنگاري فعاليت مي كند.)قبل از پيشنهاد هاي اين افراد به اين نتايج رسيده بود.
· معمولا الگوريتم هاي كليد عمومي بسيار كند تر از الگوريتم هاي كليد متقارن هستند.
· يك خصيصه ي قطعي كليد عمومي اين است كه كليد خصوصي از كليد عمومي قابل تعيين نباشد.و در مقابل حملات ”متن سادهِ انتخاب شده” مقاوم باشد.
· در واقع تركيبي از سيستمهاي رمزگذاري كليد عمومي و متقارن كاربرد دارند.
· RSA نوعي از الگوريتم رمز گذار بر پايه ي كليد عمومي است كه در گستره وسيعي از كاربردها به كار مي رود.پس اجازه دهيد در درباره RSA بحث كنيم و بعد دوباره به بحث كلي درباره كليد عمومي برگرديم.
ملزومات: تعيين كليد رمزگشايي از كليد رمزگذاري بايد غير ممكن باشد.
انتخابي: هر كدام از دو كليد عمومي و خصوصي را بايد بتوان براي رمز گذاري و رمز گشايي به كار برد.
توابع درب تله اي يا يك طرفه:
· سيستم هاي رمز گذاري كليد عمومي بر پايه ي يك سري حيله هاي زيركانه ي رياضي كه با قدرت كامپيوتر در ارتباطند گسترش يافته اند.
· رمزگذاري كليد عمومي بر پايه ي مسئله كه در رياضي با نام ”درب تله اي” شناخته مي شود كار مي كند.
· يك درب تله اي يك فرمول رياضي است كه به آساني جلو مي رود ولي برگشت آن تقريبا غير ممكن است.
· به عنوان مثال عمل ضرب كردن دو عدد بزرگ كار راحتي است ولي بدست آوردن فاكتور هاي اوليه ي آن عدد بزرگ بسيار مشكل است.
· الگوريتم كليد عمومي بر اين اساس كار مي كند كه شخصي يك كليد عمومي بزرگ را انتشار مي دهد و ديگران قادر نيستند كه فاكتور هاي اوليه ي اين كليد را بدست آورند.
· سازنده ي كليد فاكتور هاي اوليه ي كليد خود را ميداند و با استفاده از اين فاكتور ها پيغام هاي ديگران را كه با استفاده از كليد عمومي خودش رمز شده اند رمز گشايي مي نمايد.
· ديگران كه فقط از كليد عمومي آگاهي دارند قادر به شناسايي كليد خصوصي نيستند.و دليل آن هم سختي تجزيه كردن عداد بزرگ مي باشد.
RSA
· تا كنون بهترين سيستم كليد عمومي شناخته شده RSA نام دارد.اسم اين سيستم رمز گذاري بر گرفته شده از نام مولف هايش است.رونالد ال رايوست و ايديا شامير و لِونارد ام ادِلمًن
· RSA توسط سه بنيان گذارش يعني رايوست و شايرمن و لونارد ام ادلمن به عنوان يك الگوريتم رمز گذاري كليد عمومي تجاري معرفي شد.امروزه اين الگوريتم توسط مرورگر هاي وب و برنامه هاي كلاينت E-Mail ،تلفن هاي همراه و شبكه هاي محلي مجازي(vpn)، برنامه هاي دسترسي ايمن (secure shell) و در خيلي از جاهاي ديگر كاربرد دارد.اين درست است كه امنيت ي كه اين الگوريتم ايجاد مي كند جاي بحث دارد ولي با انتخاب كليد به اندازه ي كافي بزرگ مي توان جلوي اغلب حمله ها را گرفت.تا همين چند وقت پيش RSA با قوانين صادرات و حق امتياز ها محدود شده بود ولي اكنون حق امتيازات منقضي شدند و قوانين صادرات ايالات متحده نيز شل شده اند.
· اين الگوريتم بر پايه يك قانون درب تله اي كه از سختي فاكتور گرفتن از اعداد بزرگ استفاده مي كند؛ قرار گرفته است.
تقابل PK وSK :
· در رمزنگاري هاي كليد مخفي كليد رمز گذاري و كليد رمز گشايي يك كليد است.بطور كلي دو تابع وجود دارد يكي تابع رمزگذاري و ديگري معكوس آن تابع رمز گشايي.
· در مقابل كليد مخفي ؛الگوريتم كليد عمومي قرار دارد.در چنين سيستمي دو كليد وجود دارد يكي كليد عمومي و ديگري كليد خصوصي.
اعداد اول چه هستند؟
· يك عدد اول؛ عددي است كه تنها بر خودش و يك قابل تقسيم باشد.
· به عنوان مثال 10 عدد اول نيست زيرا بر اعداد 1و2و5 و10 بخش پذير است.ولي 11 يك عدد اول است زيرا تنها به خودش و 1 بخش پذير است.
· اعدادي كه يك عدد بر آنها بخش پذير است فاكتور هاي آن عدد خوانده مي شود.فرايند پيدا كردن فاكتورها فاكتور گرفتن يا تجزيه نام دارد.
· براي مثال تجزيه ي عدد 15 مي گوييم اين عدد از 3*5 بدست مي آيد ولي در مورد 6320491217 چطور؟
· حال در مورد يك عدد 155 رقمي چطور؟يا 200 رقمي يا بيشتر؟به طور خلاصه تجزيه كردن اعداد قطعا از تعدادي مرحله تشكيل شده كه تعداد اين مراحل بابزرگ شدن عدد به صورت نمايي بالا مي رود.اگر يك عدد به مقدار كافي بزرگ باشد؛ زمان مورد نياز براي اجراي تمام مراحل تجزيه كردن ممكن است به قدري زياد باشد كه سالها به طول بيانجامد.
حساب پيمانه اي:
در رياضيات پيمانه اي تنها اعداد صحيح غير منفي كوچكتر از پيمانه مورد بررسي قرار مي گيرد.پس براي پيمانه ي n (mod N) تنها اعداد صحيح كه از 0 تا (N-1) قابل حساب هستند و نتايج محاسبات تنها از 0 تا (N-1) قابل قبول است.فكر كنيد زمان نظامي بر عددي بر پيمانه ي 2400 است.براي مثال 2200 بعلاوه 400 (10:00 PM plus 4 hours)جواب 2600 نمي شود.شما از صفر شروع مي كنيد.بنابراين 2200+400 mod 2400 را بايد محاسبه كنيم كه مي شود:2600-2400=0200 و يا 2:00 صبح. همچنين اگر از 0 يا نصف شب شروع كنيم.شش برابر 500 (بخوانيد شش بار 5 ساعت به جلو)3000 نميشود.جواب 0600 يا 6:00 بعد از ظهر مي شود.اين حساب دقيقا مثل ساعت عمل ميكند.
A mod b=r به اين معني كه a بر b تقسيم شده است و باقي مانده r است.
براي مثال :
”mod همان باقيمانده تقسيم است.“
22 mod 3 = 1
34 mod 2 = 0
18 mod 5 = 3
-4 mod 3 = 2 because (3)(-2) + 2 = -4
-16 mod 7 = 5 because (7)(-3) + 5 = -16
· اعداد اول وقتي در رياضيات پيمانه اي بكار گرفته مي شوند ؛ داراي خواص سودمندي مختلفي هستند.
· الگوريتم RSA از اين خواص استفاده مي كند.

تحليل امنيت rsa :
· امتحان كردن تك تك كليد ها اگر طول كليد بين 1024 تا 2048 باشد غير ممكن است.
· بهترين انتخاب اين است كه سعي كنيم تا n را به عواملش كه pوq باشند تجزيه كنيم وسپس d را بدست بياوريم.
· اين عمل تجزيه چقدر مشكل مي باشد؟كسي ميداند؟براي يك كليد 200 رقمي زمان اين تجزيه هزاران سال تخمين زده شده است.
· اما هيچ كس اثبات نكرده است كه نمي شود در زمان معقولي اين عمل را انجام داد.
· هر كسي كه بخواهد d را بدست بياورد بايد ابتدا j(n) را بدست آورد اما براي دانستن آن نيز نياز به دانستن pوq مي باشد.كه براي بدست آوردنشان بايد n را تجزيه كرد.كه اين كار يك تابع يك طرفه است آيا به خاطر داريد؟ما ميدانيم ضرب اعداد اول بزرگ مي تواند يك تابع يك طرفه باشد. ما نياز به چيز ساده اي براي تفهيم اين واقعيت داريم.
عيب هاي RSA :‍
· امروزه كليد هاي 512 بيتي ضعيف فرض مي شوند.كليد هاي 1024 بيتي تقريبا براي اكثر اهداف به اندازه ي كافي ايمن است.و كليد 2048 بيتي ميتواند تا براي دهه هاي آينده ايمن فرض شود.
· چيزي كه بايد گفته شود اين است كه rsa نسبت به حملات متن ساده ي انتخابي بسيار ضعيف عمل مي كند.اين روش نيز يكي از روش هاي جديد ووقت گير حمله است.كه مي تواند براي موارد مختلف rsa استفاده شود.الگوريتم rsa الگوريتمي مورد قبول و ايمن است اگر از آن به درستي استفاده شود.بايد به دقت از اين الگوريتم استفاده شود.
اعداد اول بزرگ:
پيدا كردن كليد بر اين اساس است كه ما بتوانيم دو عدد اول بزرگ را انتخاب كنيم.ما عدد اول خود را از مجموعه ي بي كراني از اعداد اول انتخاب مي كنيم.براي اثبات اين كه ما بي نهايت عدد اول داريم فرض ميكنيم كه تعداد محدودي عدد اول داريم.سپس تمام اين اعداد را در يك ليست مي نويسيم و در هم ضرب مي كنيم و يكي به آن اضافه مي كنيم. اين عدد بر هيچ كدام از اعداد واقع در ليست قابل قسمت نيست پس يا اول است يا بر عدد اولي بزرگ تر از اعداد درون ليست بخش پذير است. واين مهم نيست كه ليست ما چه اندازه باشد هميشه عدد ديگري يافت مي شود. كه اين خود ثابت مي كند بي نهايت عدد اول وجود دارد.پس ما عدد اول مان را از يك مجموعه ي بي كران انتخاب مي كنيم.
اعداد اول در چه حد بزرگ باشند؟
دو عدد اول pوq كه پيمانه را مي سازند بايد به طرز فجيعي بلند باشند.اين سبب مي شود كه پيمانه بسيار سخت تر از حالتي كه يكي از اعداد اول كوچك باشد تجزيه شود.به همين دليل اگر كسي از پيمانه 768 بيتي استفاده كرد اعداد اول هر كدام بايد طولي به طور تقريبي برابر 384 داشته باشند.اگر دو عدد اول خيلي نزديك هم باشند (در حد 100 تا 200 بيت اشكالي ايجاد نمي كند) يك ريسك امنيتي بالقوه ايجاد شده است.ولي احتمال اين كه اين دو عدد بسيار نزديك به هم باشند ناچيز است.
امضاي دجيتالي باRSA :
· براي اين كه الگوريتم كار كند داريم: DKPvt(EKPub(P))=P
· rsa اين قابليت را نيز دارد : DKPub (EKPvt (P))=P
وقتي كه متن را بتوان با KPvt رمز كرده و سپس با Kpub رمز گشايي كرد.اين به rsa اين امكان را مي دهد كه از امضا ها براي تائيد استفاده كند.وقتي كه يك بلاك از داده با كليد خصوصي رمز شده باشد.هر كسي مي تواند با كليد عمومي آن را باز كند و گيرنده مي تواند اعتبار فرستنده را از طريق امضاي او شناسايي كند.
موارد استفاده فعلي rsa :
RSA در حال حاضر در گستره ي گوناگوني از محصولات ، پلت فرم ها و صنايع در سراسر جهان مورد استفاده قرار مي گيريد.اين الگوريتم در نرم افزار هاي مختلف قالب ريزي شده و براي برنامه هاي زيادي نيز در دست ايجاد است.rsa توسط سيستم هاي عامل رايجِ ساخته شده توسط ميكروسافت،اپل،سان. ناول مورد استفاده قرار گرفته شده است.در سخت افزار نيز rsa در سيستم هاي ايمن تلفن ، بر روي كارت هاي اترنت شبكه و بر روي كارت هاي هوشمند بكار گرفته شده است.
همچنين rsa با تمام پروتكل هاي اصلي شبكه براي ايجاد ارتباط هاي اينترنتي ايمن تركيب شده است . به عنوان مثال S/MIME, SSL and S/WAN همچنين از آن در داخل بسياري از سازمان هاي حقوقي نيز استفاده شده است مثلا در دولت ايالات متحده،شركت هاي بزرگ،آزمايشگاه هاي ملي و دانشگاه ها.حق امتياز RSA را بيش از 350 شركت گرفته اند.همچنين تخمين زده مي شود كه ماشين هاي ايجاد شده بر مبناي RSA در حدود350 ميليون است.واين نشان مي دهد كه RSA به سرعت و متناسب با سرعت رشد اينترنت و وب گسترش ميابد.
Rsa چقدر سريع است؟
در مقام مقايسه ؛DES وديگر الگوريتم هاي متقارن بسيار سريع تر از rsa عمل مي كند.در نرم افزار DES معمولا 100 برابر سريع تر از RSA است.در سخت افزار نيز DES 1000 تا 10000 برابر سريع تر است.البته بستگي به نحوي اجرا دارد.در عمل rsa ممكن است تبديل به يك گلوگاه شود ولي DES به خوبي و با سرعت عمل مي نمايد.
 

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
الگوریتم ممتیک متاهیوریستیکِ جهش ترکیبی قورباغه

الگوریتم ممتیک متاهیوریستیکِ جهش ترکیبی قورباغه

پژوهشی مبتنی بر الگوریتم ممتیک متاهیوریستیکِ جهش ترکیبی قورباغه
چکیده- الگوریتم جهش ترکیبیِ قورباغه (SFLA) یک الگوریتم تکاملی و مبتنی بر جمعیتِ متاهیوریستیک جدید است. این الگوریتم سریع است و قابلیت جستجوی سراسری بسیار خوبی دارد. در این مقاله در ابتدا قاعده­ی کلی الگوریتم SFLA مطرح می­شود و سپس پارامترهای آن مورد تحلیل قرار می­گیرند. بوسیله­ی آزمایش، پارامترها به گونه­ای انتخاب می­شوندکه تاثیر مثبتی بر SFLA داشته باشند. الگوریتم SFLA با استفاده از تابع آزمایش، با الگوریتم ژنتیک (GA) و بهینه­سازیِ گروه ذرات (PSO) مقایسه می­شود. آزمایشات نشان می­دهند که دقت و قابلیت جستجوی سراسریِ SFLA از GA و PSO بهتر است.
1.مقدمه
الگوریتم جهش ترکیبیِ قورباغه (SFLA) یک الگوریتم مبتنی بر ممتیک متاهیوریستیک است. این الگوریتم در سال­های اخیر توسط Eusuff و Lansey ایجاد شد. الگوریتم SFLA از نحوه­ی جستجوی غذای گروه­های­ قورباغه­ سرچشمه می­گیرد. این الگوریتم برای جستجوی محلی میان زیرگروه­­های قورباغه از روش نمو ممتیک استفاده می­کند. SFLA از استراتژیِ ترکیب استفاده می­کند و امکان مبادله پیام در جستجوی محلی را فراهم می­سازد. این الگوریتم مزایای الگوریتم نمو ممتیک و بهینه­سازیِ گروه ذرات (PSO)[1] را ترکیب می­کند. در SFLA نه تنها در جستجوی محلی بلکه در جستجوی سراسری نیز پیام­ها مبادله می­شوند. بدین ترتیب جستجوی محلی و سراسری به خوبی در این الگوریتم ترکیب می­شوند. جستجوی محلی امکان انتقال مم را میان افراد ممکن می­سازد و استراتژیِ ترکیب امکان انتقال مم را میان کل جمعیت ممکن می­سازد. مانند الگوریتم ژنتیک (GA) و بهینه­سازی گروه ذرات (PSO) الگوریتم جهش ترکیبیِ قورباغه یک الگوریتم بهینه­سازیِ مبتنی بر کولونی است. SFLA قابلیت بالایی برای جستجوی سراسری دارد و پیاده­سازیِ آن آسان است. الگوریتم SFLA می­تواند بسیاری از مسائل غیرخطی، غیرقابل­تشخیص[2] و چندحالته[3] را حل کند. این الگوریتم به مراتب برای حل مساله­ی توزیع منابع آبی بکارگرفته می­شود.



2.الگوریتم ترکیبی جهش قورباغه
A. قاعده­ی کلیِ SFLA
الگوریتم SFLA ترکیب روش قطعی و روش تصادفی است. روش قطعی به الگوریتم امکان می­دهد تا پیام­ها را به صورت کارایی مبادله کند. روش تصادفی انعطاف­پذیری و مقاومت الگوریتم را تضمین می­­کند. الگوریتم با انتخاب تصادفی گروه­های قورباغه شروع می­شود. گروه­های قورباغه به چندین زیرگروه تقسیم می­شوند. هر یک از این زیرگروه­ها می­توانند جستجوی محلی را به صورت مستقل و با روش­ متفاوتی انجام دهند. قورباغه­های موجود در یک زیرگروه می­توانند بر روی سایر قورباغه­های موجود در همان زیرگروه اثر بگذارند. بدین تریب قورباغه­های موجود در یک زیرگروه تکامل می­یابند. تکامل ممتیک کیفیت ممتیکِ قورباغه­های منفرد را بهبود و قابلیت دستیابی به هدف را افزایش می­دهد. برای رسیدن به یک هدف خوب می­توان وزنِ قورباغه­ها­ی خوب را افزایش و وزن قورباغه­های بد را کاهش داد. بعد از تکامل برخی از ممتیک­ها، زیرگروه­ها با هم ترکیب می­شوند. بواسطه­ی ترکیب ممتیک­ها در حوزه­ی سراسری بهینه می­شوند و بوسیله­ی مکانیزم ترکیب زیرگروه­های قورباغه­ی جدیدی ایجاد می­شود. ترکیب، کیفیتِ ممتیک­هایی که تحت تاثیرِ زیرگروه­های مختلف قرار می­گیرند را افزایش می­دهد. جستجوی محلی و جستجوی سراسری تا برآورده شدن شرط همگرایی ترکیب می­شوند. توازن بین مبادله پیام سراسری و جستجوی محلی به الگوریتم امکان می­دهد تا به راحتی از مینیمم محلی پرش کند و تا دستیابی به بهینه­سازی توسعه یابد. یکی از خصیصه­های الگوریتم SFLA همگرایی سریع آن است.

 

پیوست ها

  • SFLA_(mathworks.ir).pdf
    731.2 کیلوبایت · بازدیدها: 0

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
زمانبندی در سیستم های گرید با استفاده از الگوریتم رقابت استعماری

زمانبندی در سیستم های گرید با استفاده از الگوریتم رقابت استعماری

يکی از بخش­­های بسيار مهم در هر سيستم گريد، زمانبند است. وظيفه زمانبند مديريت منابع و تقسيم صحیح وظايف مابين منابع محاسباتی است. همچنين کنترل خطا از جمله­ وظايف اين مؤلفه است. زمانبندی بهتر باعث بالا رفتن بیشتر کيفيت سرويس می­شود. برای زمانبندی از روشهای مختلفی می­توان استفاده کرد. هدف از تعریف این پروژه ابتدا مطالعه و بررسی تعدادی از الگوريتمهای بهينه­سازی اِکتشافی و سپس پیاده­سازی و مقایسه آن­ها با یکدیگر است. الگوريتم­های موجود را می­توان به دو کلاس برخط[1] و دسته­ای[2] تقسيم نمود. در حالت برخط، هر وظيفه به محض رسيدن به زمانبند گريد، به منبع يا ماشين مناسب (از نظر زمانبند و استراتژی آن) تخصيص داده می­شود؛ اما در حالت دسته­ای وظايف بلافاصله زمانبندی نمی­شوند بلکه به صورت گروه یا مجموعه­ای از وظايف درآمده و با يک دوره تناوب خاص، عمل زمانبندی بر روی آنها صورت می­گيرد؛ در واقع عمل زمانبندی به صورت گروهی و دسته­ای انجام می­شود. الگوريتمهای برخط در شرايطی که نرخ ورود وظايف به محيط پايين باشد مناسب­اند و برعکس درباره راه­بردهای دسته­ای بهتر است نرخ ورود وظايف بالا باشد. واضح است که در مورد محيط گريد، پويايي زياد آن باعث می­شود که الگوريتمهای دسته­ای عملکرد بهتری داشته باشند.
الگوریتم رقابت استعماری (Imperialist Competitive Algorithm - ICA) روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینه سازی می‌پردازد. این الگوریتم با مدلسازی ریاضی فرایند تکامل اجتماعی - سیاسی، الگوریتمی برای حل مسائل ریاضی بهینه سازی ارائه می‌دهد . از لحاظ کاربرد، این الگوریتم در دسته الگوریتم های بهینه سازی تکاملی همچون الگوریتم­های ژنتیک (Genetic Algorithms)، بهینه سازی انبوه ذرات (Particle Swarm Optimization)، بهینه سازی کلونی مورچگان (Ant Colony Optimization)، تبرید فلزات شبیه سازی شده (Simulated Annealing) و ... قرار می گیرد. همانند همه الگوریتم های قرار گرفته در این دسته، الگوریتم رقابت استعماری نیز مجموعه اولیه ای از جوابهای احتمالی را تشکیل می دهد. این جوابهای اولیه در الگوریتم ژنتیک با عنوان "کروموزوم"، در الگوریتم ازدحام ذرات با عنوان "ذره" و در الگوریتم رقابت استعماری نیز با عنوان "کشور" شناخته می شوند. الگوریتم رقابت استعماری با روند خاصی که در ادامه می آید، این جوابهای اولیه (کشور ها) را به تدریج بهبود داده و در نهایت جواب مناسب مسئله بهینه سازی (کشور مطلوب) را در اختیار می گذارد.
پایه‌های اصلی این الگوریتم را سیاست همسان سازی (Assimilation)، رقابت استعماری (Imperialistic Competition) و انقلاب (Revolution) تشکیل می‌دهند. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدلسازی ریاضی بخشهایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه سازی کمک کنند. در واقع این الگوریتم جوابهای مسئله بهینه سازی را در قالب کشورها نگریسته و سعی می‌کند در طی فرایندی تکرار شونده این جواب‌ها را رفته رفته بهبود داده و در نهایت به جواب بهینه مسئله برساند.

[1] Online mode
[2] Batch Mode​
منابع: http://en.wikipedia.org/wiki/Imperialist_competitive_algorithm
 

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
درخت های تصمیم گیری: الگوریتم ID3

درخت های تصمیم گیری: الگوریتم ID3

درخت های تصمیم گیری: الگوریتم ID3برای دسته بندی اطلاعات و نیز فرآیند انتخاب های ماشینی می توان از الگوریتم های تصمیم گیری استفاده کرد ، به طور مثال در ما می توانیم مقداری از اطلاعات را به یک کامپیوتر بدهیم و سپس از آن بخواهیم با گرفتن اطلاعات بعدی (بر اساس اطلاعات قبلی) برای ما تصمیم گیری کند. یکی از الگوریتم های موجود الگوریتم ID3 نام دارد که در سال 1975 توسط J. Ross Quinlan و در کتابMachine Learning معرفی شد.به طور ساده یک الگوریتم id3 از تعدادی داده ثابت برای ما یک درخت تصمیم گیری می سازد که این درخت برای طبقه بندی کردن اطلاعات و در نتیجه تصمیم گیری به کار می روند . مثال هایی که ما به کامپیوتر می دهیم شامل تعدادی مشخصات و تعدادی کلاس هستند. به طور مثال وقتی می گوییم یک مرد باید از 170 سانتیمتر بلند تر باشد ، دو مولفه ی کلاس و مشخصه را تعریف کرده ایم که در اینجا مشخصه "اندازه ی قد" و کلاس "مرد بودن" است و یا ممکن است بگوییم یک زن حتما موهایی بلندتر از 30 سانتی متر دارد که در اینجا "اندازه ی مو" مشخصه و نیز "زن بودن" کلاس است.انتخاب مشخصه ی کلاس بندیالگوریتم id3 از کجا می فهمد که باید بر اساس کدام مشخصه اطلاعات را طبقه بندی کند؟جواب در یک متغییر آماری به نام ig و یا همان ضریب اطلاعات خلاصه شده است که این ضریب مشخص می کند که یک مشخصه "چقدر خوب؟"می تواند اطلاعات را دسته بندی کند و به این صورت بهترین مشخصه انتخاب می شود تا بر اساس آن طبقه بندی اطلاعات صورت گیرد یعنی همان مشخصه ای که ig بیشتری داشته باشد برای آنکه بتوانیم ig را تعریف کنیم باید از تئوری اطلاعات و نیز مفهوم آنتروپی استفاده نماییم (اگر با این مفهوم آشنا نیستید نگران نباشید زیرا نیازی به جزئیات نیست). آنتروپی میزان اطلاعاتی است که درون یک مشخصه گنجانده شده است و با فرمول زیر اندازه گیری می شود:


Entropy(S) = S -p(I) log2 p(I)
که در اینجا p(I) سهم نوع S در مجموعه ی I است.S مجموعه ی اطلاعاتی است که به کامپیوتر داده می شود تا بر اساس آنها درخت تصمیم گیری را بسازد. در حقیقت آنتروپی نشان می دهد که تا چه حد اطلاعات دسته بندی شده اند. اگر آنتروپی به سمت صفر بروند یعنی اطلاعات کاملا دسته بندی شده اند .به طور مثال مجموعه ای داریم که شامل 14 عضو است که در این مجموعه 9 yes و 5 no وجود دارد.آنتروپی مجموعه به صورت زیر حساب می شود:
Entropy(S) = - (9/14) Log2 (9/14) - (5/14) Log2 (5/14) = 0.940
- Ig برای یک مجموعه از مثال (در اینجا s)به صورت زیر حساب می شود:
Gain(S, A) = Entropy(S) - S ((|S[SUB]v[/SUB]| / |S|) * Entropy(S[SUB]v[/SUB]))

که در آن :
s = تعداد کل اعضای مجموعه ی sS[SUB]v[/SUB] = زیر مجموعه ای از S که مقدار مشخصه ی A آنها برابر v است.|S[SUB]v[/SUB]| = اندازه زیر مجوعه|S| = اندازه مجموعهمثال : فرض کنید مجموعه ی s شامل 14 مثال است که یکی از مشخصات آنها باد است که باد می تواند ضعیف یا قوی باشد که نتایج این اطلاعات شامل 5 YES و 4 NO است. برای مشخصه ی باد 8 رخداد ضعیف و 6 رخداد قوی داریم و برای مشخصه ی باد ضعیف 6 نتیجه YES و 2 نتیجه ی NO داریم
Gain(S,Wind)=Entropy(S)-(8/14)*Entropy(S[SUB]weak[/SUB])-(6/14)*Entropy(S[SUB]strong[/SUB])
0.940 - (8/14)*0.811 - (6/14)*1.00=
0.048=
Entropy(S[SUB]weak[/SUB]) = - (6/8)*log2(6/8) - (2/8)*log2(2/8) = 0.811
Entropy(S[SUB]strong[/SUB]) = - (3/6)*log2(3/6) - (3/6)*log2(3/6) = 1.00
برای هر کدام از مشخصات ضریب حساب می شود و مشخصه ای که دارای بیشترین ضریب است به عنوان بهترین مشخصه برای طبقه بندی انتخاب می شود.مثال معروف بازی کردن بیس بال:فرض کنید که به وسیله ی الگوریتم می خواهیم تشخیص دهیم که آیا هوا برای بازی کردن بیس بال خوب است یا نه؟در دوره ی دو هفته ای از بازی کردن بیس بال اطلاعات زیر جمع آوری شده است این اطلاعات به id3 کمک می کند تا یک درخت تصمیم گیری ساخته شود. هدف ساختن در ختی است که تعیین کند که آیا باید در یک روز با اطلاعات خاص بیس بال بازی کنیم یا نه؟اطلاعات شامل :نوع هوا{آفاتابی ، ابری ، بارانی}دما {گرم ، معتدل ، سرد}رطوبت {زیاد، کم}شدت باد {قوی ، ضعیف}مجموعه اطلاعات داده شده که به نام S شناخته می شوند شامل اطلاعات زیر هستند:

Day​
Outlook​
Temperature​
Humidity​
Wind​
Play ball​
D1SunnyHotHighWeakNo
D2SunnyHotHighStrongNo
D3OvercastHotHighWeakYes
D4RainMildHighWeakYes
D5RainCoolNormalWeakYes
D6RainCoolNormalStrongNo
D7OvercastCoolNormalStrongYes
D8SunnyMildHighWeakNo
D9SunnyCoolNormalWeakYes
D10RainMildNormalWeakYes
D11SunnyMildNormalStrongYes
D12OvercastMildHighStrongYes
D13OvercastHotNormalWeakYes
D14RainMildHighStrongNo

ابتدا باید بفهمیم که کدام یک از مشخصات ریشه ی درخت تصمیم گیری هستند؟
برای این منظور باید آنتروپی تمامی مشخصات را حساب کنیم.
Gain(S, Outlook) = 0.246
Gain(S, Temperature) = 0.029
Gain(S, Humidity) = 0.151
Gain(S, Wind) = 0.048 (calculated in example 2)

بیشترین ضریب مربوط به نوع هوا است (Oultlook) ، بنا بر این به عنوان ریشه درخت ما مورد استفاده قرار می گیرد.به خاطر اینکه نوع هوا شامل 3 مقدار است پس درخت تصمیم گیری شامل 3 شاخه می شود .سوال بعدی این است که در شاخه ی نوع هوای آفتابی چه نوع تصمیم گیری باید انجام شود ؟برای پاسخ به این سوال باید از ضریب اطلاعات استفاده شود و باید مشخص کنیم که در مجموعه هوای آفتابی کدام یک از متغییر های دیگر دارای پراکندگی اطلاعات کم تری هستند و در حقیقت igبالاتری دارند.

S[SUB]sunny[/SUB] = {D1, D2, D8, D9, D11} = 5 examples from table 1 with outlook = sunny
Gain(S[SUB]sunny[/SUB], Humidity) = 0.970
Gain(S[SUB]sunny[/SUB], Temperature) = 0.570
Gain(S[SUB]sunny[/SUB], Wind) = 0.019
که در اینجا رطوبت دارای بیشترین ضریب است و به عنوان مشخصه تصمیم انتخاب می شود و این فرآیند ادامه پیدا می کند تا زمانی که مشخصات ما به اتمام برسد.

منبع: matlab-pro.blogfa.com
 

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
روش پرتوربیشن

روش پرتوربیشن

بسیاری از پدیده های اطراف ما به طور ذاتی غیر خطی هستند و با معادله های غیر خطی بیان یا توصیف می شوند. از زمان ظهور کامپیوتر های دیجیتالی، هر روزه حل معادلات خطی آسانتر میشود واین در حالی است که برای بسیاری از معادلات غیر خطی جواب دقیقی وجود ندارد. در بسیاری از موارد یافتن حل تحلیلی [1]معادلات غیر خطی بسیار مشکل تر از بدست آوردن حل عددی آن میباشد، با وجود این هم اکنون با پیشرفت سخت افزار و وجود ابر کامپیوتر ها و برنامه های بسیار قدرتمندی همانند Maple و Mathematica که با متغیر های سمبولیک[2] کار میکنند، حل بسیاری از معادله ها آسانتر شده است. حل عددی به طور عمومی می تواند با محاسبات پیچیده کامپیوتری معادلات غیر خطی را حل نماید؛ این یک برتری حل عددی نسبت به حل تحلیلی میباشد که قادر است در بعضی از مواقع مسایل غیر خطی را ساده تر حل نماید. اگرچه حل عددی نقاط ناپیوستگی یک نمودار را نمایان میسازد اما با وجود این گاهی اوقات برای دریافت کل جواب بسیار هزینه بر و وقت گیر است و همچنین در کنار نتیجه های عددی، درک ماهیت مساله غیر خطی مشکل میشود. مشکلات حل عددی موقعی ظاهر میشود که مساله غیر خطی دارای تکینگی یا جواب های چند گانه باشد. حل عددی و تحلیلی مسائل غیر خطی مزایا و معایب جداگانه خود را داراست و همچنین محدودیت های خود را دارد. بنابراین این امر غیر ضروری است که ما یک روش را برگزینیم و از دیگری صرف نظر نماییم. عموماحل تحلیلی مسایل برای در بسیاری از موارد مطلوب میباشد.
بعضی راه حل های تحلیلی برای حل مسایل غیر خطی وجود دارد، پرتوربیشن تکنیک



[3] یکی از آنهاست [2،3،4،5،6،7،8،9،10،11]که به صورت گسترده و به سزایی در موارد مختلفی به کار رفته است. به وسیله ی روش پرتوربیشن بسیاری از مسائل و خاصیت های پدیده های غیر خطی آشکار گردیدند. یکی از موفقیت های چشمگیر روش پرتوربیشن موفقیت در کشف سیاره ی نهم منظومه شمسی بود که در آسمان بی کران جهان در نقطه ای که با حل معادلات ریاضی پیش بینی شده بود هویدا گردید. اخیراروش پرتوربیشن تکین[4] یکی از 10 تا پیشرفت اساسی برای مکانیک در قرن بیستم بوده است.برای همه گان مشهود است که پرتوربیشن نقش بسزایی در پیشرفت علوم مهندسی و علوم محض داشته است به همین علت برای خواننده عزیز چندین مرجع از روش پرتوربیشن که در خط های قبلی معرفی شده بود قرار داده شده است.
روش پرتوربیشن به طور ذاتی بر اساس وجود پارامتر های کوچک و بزرگ موجود در مساله که به مقادیر پرتوربیشن[5] معروف هستند. یا به بیان عامیانه تر، روش پرتوربیشن از مقادیر پرتوربیشن برای تبدیل مسائل غیر خطی به تعداد مشخصی از مسائل خطی استفاده می کند تا بتواند جواب ساله غیر خطی را به صورت مجموعه ای از مسائل خطی حل شده در آورد. در واقع مقادیر پرتوربیشن سنگ زیربنایی روش پرتوربیشن هستند و همین مقادیر پرتوربیشن هستند که برای این روش محدودیت ایجاد میکند. لذا باید گفته شود که: اولا، این غیر ممکن است که تمام مسائل غیر خطی دارای چنین مقادیر پرتوربیشنی باشد و ثانیا، تقریب تحلیل چنین مسائلی در موارد متعددی که عامل غیر خطی قوی وجود دارد به شکست می انجامد و روش پرتوربیشن برای مواردی کاربرد دارد که غیر خطی بودن ضعیف میباشد و هر دو عامل ذکر شده دلایل مبرهنی برای ارائه ی محدودیت های روش پرتوربیشن میباشد. برای مثال به مساله ی درگ یک کره جامد که درون یک جریان یکنواخت غوطه ور شده است توجه کنید. این مساله یک مساله غیر خطی کلاسیک مکانیک سیالات می باشد که معادلات ناویر استوکس بر آن حاکم است. در سال 1851 وقتی که استوکس این مساله را مورد مطالعه قرار داد. بسیاری از دانشمندان آن زمان به نظریه ی او با تئوری های خطی حاکم در آن زمان به مخالفت برخواستند مخصوصا با روش پرتوربیشن و مقایسه آن با حل هایی که از پرتوربیشن بدست می آوردند. و این در حالی بود که تمام مقادیر بدست آمده فقط برای مقادیر رینولدز کوچک باروش های تجربی همخوانی داشت. بنابر این همه ی اینها از این واقعیت حکایت دارد که پرتوربیشن نمیتواند برای ما روشی ارائه دهد که محدوده ی همگرایی را تعیین نماید و همچنیین نمیتواند جواب مساله را در خیلی از موارد تقریب نماید.بعضی از روش های محدودی علاوه بر پرتوربیشن نیز وجود دارد. همانطور که گفته شد وابستگی روش پرتوربیشن به پارامترهای بزرگ و کوچک بود. وابستگی روش پرتوربیشن را به این مقادیر را میتوان با اضافه کردن یک متغیر معروف به متغیر کوچک مصنوعی[6] از بین برد. در سال 1892 لیاپونو[7] معادله ی زیر را مورد مطالعه قرار داد:
(1-1) dx/dt=A(t)x​
جایی که A(t) ماتریکس زمانی است. لیاپونو متغیر کمکی ε را برای حل معادله به کار برد ومعادله (2-2) را با معدله (1-1) حایگزین نمود
(1-2) dx/dt=eps.A(t).x​
و سپس جوابی بر اساس بسط توانی ε ارائه داد. در بسیاری از موارد لیاپونو اثبات کرد که سری به ازای همگرا می شود. دستاورد بالا را روش لیاپانو می نامند. این ایده بعد ها توسط کارمیشین[8] بسط و گسترش داده شد و به روش بسط دلتا[9] معروف گردید. کارمیشین بعد ها پارامتر δ را در معادله ی زیر به کار برد تا
(1-3) x^5+x=1​
به معادله زیر تبدیل شود
(1-4) x^(1+del)+x=1​
و سپس سری توانی گسترش یافته δ را بدست آورد و در نهایت تقریب آخر را با تبدیل سری δ به تقریب زننده یpade که همچون عملگری باعث سریعتر شدن همگرایی میشود بدست آورد. باید توجه داشت که ذاتا روش بسط با روش متغیر کوچک کمکی لیاپانو دلتا برابر میباشد. باید توجه داشت که هر دو روش با تولید یک متغیر کمکی به جواب میرسند، در حالی که تفاوت این دو فقط در این است که هر دو در قسمت های مختلف معادله ظاهر میشوندو اسم متفاوتی دارند ولی از لحاظ ماهیت یکی هستند. همچنین با توجه به روش کارمیشین ما میتوانیم مقدار متغیر کمکی را در هر جای معادله قرار دهیم لذا معادله ی (1-3) می تواند به زیر تغیر یابد
(1-5) del.x^5+x=1​
تقریب که بوسیله ی معادله ی بالا به دست می آید بسیار بدتر از تقریبی است که از معادله(1-6) به دست می آید.هر دوی روش های دلتا و متغیر کوچک لیاپانو نیازمند قواعدی است تا مشخص نماید که پارامتر کمکی δ و ε در کجای معادله به کار گرفته شوند. هماند پرتوربیشن هر دو روش بسط و متغیر کوچک لیاپانو به تنهایی نمیتوانند روش مشخصی را برای حل مسائل غیر خطی ارائه دهند و همچنین روش مشخصی را برای ارائه ی ناحیه ی همگرایی و مقدار تقریب را نمیدهند.
روش تجزیه ی آدمین[10] [12،13،14] یک روش بسیار قوی برای حل مسائل غیر خطی قوی میباشد. اصول ایده ی آدمین برای ارائه حل خود بسیار شبیه به شیوه های روش های هموتوپی[11] آنالیز و هموتوپی پرتوربیشن[12] که پیشتر توضیح داده خواهد شد میباشد. روش آدمین هم برای معدلات دیفرانسیل عادی و هم جزیی قابل استفاده میباشد، با وجود این روش آدمین یک سری محدودیت هایی دارد که این روش را دچار مشکلات عدیده ای میکند. تقریبهایی که بوسیله ی روش آدمین زده میشود گاهی اوقات دارای چند جمله های توانی میباشد. در حالت عمومی میشود گفت که ناحیه ی همگرایی سریهای توانی معمولا کوچک میباشد، بنابراین روش های تسریع دهنده لازم است به کار رود تا ناحیه ی همگرایی را بیشتر و بزرگتر نماید. این مشکلات بیشتر به خاطر آن است که میشود گفت که سریهای توانی همیشه توابع اساسی برای تقریب زدن یک معادله غیر خطی نمی باشند، اما متاسفانه روش آدمین به ما ازادی عمل برای انتخاب توابع اساسی اولیه را نمی دهد. همانند روش متعیر کوچک لیاپانو و روش بسط دلتا ، روش تجزیه ی آدمین به تنهایی نمیتواند برای ما یک روش راحت برای حل مسائل ارئه دهد.
به طور کلی میتوان نتیجه گرفت که هیچ کدام از روشهای پرتوربیشن و روش های غیره مانند روش متغیر مصنوعی کوچک لیاپونو و روش بسط دلتا و روش تجزیه ی آدمین نمیتواند یک روش مناسب و راحت برای تنظیم وتقریب سریهای جواب ارائه نمی دهد. تاثیر روش های تقریبی در حل مسائل هنوز به صورت کلی جایگاه خود را پیدا نکرده است. لذا اخیر یک سری روش های جدید برای حل این مسائل ارائه شده است که دارای قابلیت های ویژه ای میباشند. حواب های این روش دارای خاصیت های زیر می باشند:
جواب آنها برای معادلات غیر خطی قوی معتبر می باشد حتی اگر معادله غیر خطی مورد نظر دارای مقادیر کوچک و بزرگ نباشد.
امکان یک روش راحت برای تنظیم کردن بازه ی همگرایی را به ما میدهد.
به ما این امکان میدهد تا توابع اولیه متفاوتی را انتخاب کنیم و همچنین امکان میدهد تا سری جوابهای خود را بر اساس توابع مشخصی بیان نماییم.
روش های جدیدی موسوم به روش آنالیز هموتوپی و هموتوپی پرتوربیشن دارای قابلیت های بالا هستند و قدرت بسیار بالایی در حل مسائل به ما ارئه میدهند. در این پروژه سعی شده است که به صورت گسترده ای در مورد روش های بالا بحث شود.
[1] Liao, Shijun, Beyond perturbation : introduction to homotopy analysis method.
[2] Cole, J.D. Perturbation Methods in Applied Mathematics. Blaisdell
Publishing Company, Waltham, Massachusetts, 1968.
[3] Von Dyke, M. Perturbation Methods in Fluid Mechanics. The Parabolic
Press, Stanford, California, 1975.
[4] Nayfeh, A.H. Introduction to Perturbation Techniques. John Wiley &
Sons, New York, 1981.
[5] Nayfeh, A.H. Problems in Perturbation. John Wiley & Sons, New York,
1985.
[6] Grasman, J. Asymptotic Methods for Relaxation Oscillations and Applications,
volume 63 of Applied Mathematical Sciences. Springer-Verlag,
New York, 1987.
[7] Lagerstrom, P.A. Matched Asymptotic Expansions: Ideas and Techniques,
volume 76 of Applied Mathematical Sciences. Springer-Verlag,
New York, 1988.
[8] Hinch, E.J. Perturbation Methods. Cambridge Texts in Applied Mathematics.
Cambridge University Press, Cambridge, 1991.
[9] Murdock, J.A. Perturbations: Theory and Methods. John Wiley &
Sons, New York, 1991.
[10] Bush, A.W. Perturbation Methods For Engineers and Scientists. CRC
Press Library of Engineering Mathematics. CRC Press, Boca Raton,
Florida, 1992.
[11] Kevorkian, J. and Cole, J.D. Multiple Scales and Singular Perturbation
Methods, volume 114 of Applied Mathematical Sciences. Springer-
Verlag, New York, 1995.
[12] Adomian, G. Nonlinear stochastic differential equations. J. Math. Anal.
and Applic., 55:441–452, 1976.
[13] Adomian, G. and Adomian, G.E. A global method for solution of complex
systems. Math. Model., 5:521–568, 1984.
[14] Adomian, G. Solving Frontier Problems of Physics: The Decomposition
Method. Kluwer Academic Publishers, Boston and London, 1994.​

[1]- analytical
[2]- symbolic
[3]- perturbation technique
[4]- perturbation singular
[5] - perturbation quantity
[6]- artificial small parameter
[7]- Lyapunov
[8]- karmishin
[9]- δ-expansion
[10]-Adomian’s decomposition method
[11] -homotopy analysis method
[12]-homotopy perturbation method
 

الهام(منو)

عضو جدید
سلام خسته نباشید
من الگوریتم حذف گوس رو میخوام .
هر کجا که می گردم پیداش نمی کنم :(
میشه کمکم کنید لطفا
 

P O U R I A

مدیر مهندسی شیمی مدیر تالار گفتگوی آزاد
مدیر تالار
سلام خسته نباشید
من الگوریتم حذف گوس رو میخوام .
هر کجا که می گردم پیداش نمی کنم :(
میشه کمکم کنید لطفا
2نمونه از الگوریتم گوس برای 6معادله و 6مجهول !!
البته این کدها خیلی مبتدی نوشته شده اند .
http://www.mediafire.com/download/h1w2npxv1wpdepc/گوس.rar
 

Similar threads

بالا