بایگانی برچسب برای: هوش ازدحامی

هوش ازدحامی یا هوش گروهی

,

هوش‌ازدحامی

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

هوش ازدحامی

روباتیک گروهی، کاربردی از اصول هوش مصنوعی گروهی در شمار زیادی از روبات‌های ارزان قیمت است.

مقدمه

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

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

رفتار گروهی، تنها وابسته به رفتار فردی گماشته‌ها و افراد اجتماع نیست بلکه به چگونگی همکنشی (interaction) و تعامل میان افراد نیز وابسته است. همکنشی بین افراد، تجربهٔ افراد دربارهٔ پیرامون (environment) را افزایش می‌دهد و مایه پیشرفت اجتماع می‌شود. ساختار اجتماعی Swarm بین افراد مجموعه کانالهای ارتباطی ایجاد می‌کند که طی آن افراد می‌توانند به داد و ستد تجربه‌های شخصی بپردازند. مدل‌سازی محاسباتی Swarmها کاربردهای امیدبخش و بسیاری را به ویژه در زمینه بهینه‌سازی (optimization) در پی داشته است. الگوریتهای فزاینده‌ای از بررسی Swarmهای گوناگون پیشنهاد شده‌اند. از این رده، می‌توان به کولونی مورچه‌ها (Ant Colony) و دستهٔ پرندگان (Bird Flocks) اشاره نمود. با اینکه دانش Swarm intelligence، دانشی نو می‌باشد؛ هم اکنون، کاربردهای رو به گسترشی از آن شناخته شده است. با این رشد روزافزون، Swarm intelligence می‌تواند نقش ارزنده‌ای را در دانشهای گوناگون بر دوش بگیرد.

الگوریتمهای هوش ازدحامی

الگوریتم مورچه‌ها

روش بهینه‌سازی گروه مورچه‌ها(Ant Colony Optimization)یکی از زیر شاخه‌های هوش ازدحامی است که در آن از رفتار مورچه‌های واقعی برای یافتن کوناه‌ترین گذرگاه میان لانه و چشمه خوراکی (food source) الگوبرداری شده است. هر مورچه برای یافتن خوراک در گرداگرد لانه به گونه تصادفی حرکت و در طی راه با بهره‌گیری از ماده شیمیایی به نام فرومن، از خود ردی بر جای می‌گذارد. هر چه شمار مورچه‌های گذر کرده از یک گذرگاه بیشتر باشد، میزان فرومن انباشته روی آن گذرگاه نیز افزایش می‌یابد. مورچه‌های دیگر نیز برای گزینش گذرگاه، به میزان فرومن آن می‌نگرند و به احتمال زیاد گذرگاهی را که دارای بیشترین فرومن است بر می‌گزینند. به این شیوه، حلقه بازخور مثبت پدید می‌آید. گذرگاه هرچه کوتاه‌تر باشد، زمان رفت و برگشت کاهش و مورچه بیشتری در یک زمان مشخص از آن می‌گذرد. از این رو، انباشت فرومن آن افزایش می‌یابد.

شایان یادآوری است که گزینش گذرگاه دارای بیشترین فرومن، قطعی نیست و احتمالی است. به همین سبب، امکان یافتن بهترین گشایش (solution) وجود دارد. روش ACO، نوعی فرااکتشافی است که برای یافتن گشایشهای تقریبی برای مسائل بهینه‌سازی آمیختاری (Combinatiorial Optimization) سودمند است. روش ACO، مورچه‌های ساختگی به‌وسیلهٔ حرکت بر روی گرافِ مسئله و با وانهادن (deposit) نشانه‌هایی بر روی گراف، همچون مورچه‌های واقعی که در گذرگاه خود نشانه‌های به جا می‌گذارند، سبب می‌شوند که مورچه‌های ساختگی بعدی بتوانند گشایشهای بهتری را برای مسئله فراهم کنند.

الگوریتم مورچه هاالگوریتم مورچه ها

بهینه‌سازی گروهی ذره

روش بهینه‌سازی ازدحام ذرات (Particle swarm optimization) یک الگوریتم جستجوی اجتماعی است که از روی رفتار اجتماعی دسته‌های پرندگان مدل شده است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینهٔ دسته به کار گرفته شد. در PSO، particleها در فضای جستجو جاری می‌شوند. تغییر مکان particleها در فضای جستجو تحت تأثیر تجربه و دانایی خودشان و همسایگانشان است. بنابراین موقعیت دیگر particleهای Swarm روی چگونگی جستجوی یک particle اثر می‌گذارد. نتیجهٔ مدل‌سازی این رفتار اجتماعی فرایند جستجویی است که particleها به سمت نواحی موفق میل می‌کنند. Particleها در Swarm از یکدیگر می‌آموزند و بر مبنای دانایی بدست آمده به سمت بهترین همسایگان خود می‌روند. Particle swarm Optimization Algorithm اساس کار PSO بر این اصل استوار است که در هر لحظه هر particle مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگی‌اش وجود دارد، تنظیم می‌کند.

فرض کنید می‌خواهیم زوج مرتب [x،y] را طوری بدست آوریم که تابع F(x،y)=x۲+y۲، مینیمم شود. ابتدا نقاطی را به صورت تصادفی در فضای جستجو، روی صفحهٔ x-y انتخاب می‌کنیم. فرض کنید این Swarm را به ۳ همسایگی تقسیم کنیم که در هر همسایگی نقاط موجود با یکدیگر تعامل دارند. در هر همسایگی هر یک از نقاط به سمت بهترین نقطه در آن همسایگی و بهترین مکانی که آن نقطه تاکنون در آن قرار داشته است، حرکت می‌کند. برای حل یک مسئله چند متغیر بهینه‌سازی می‌توان از چند Swarm استفاده کرد که هر یک از Swarmها کار مخصوصی را انجام می‌دهند. این همان ایده‌ای است که Ant colony از آن ریشه می‌گیرد. روش PSO یک الگوریتم روش جستجوی سراسری (global search algorithm) است که با بهری گیری از آن می‌توان با مسائلی که پاسخ آنها یک نقطه یا سطح در فضای n بعدی می‌باشد، برخورد نمود. در اینچنین فضایی، فرضیاتی مطرح می‌شود و یک سرعت ابتدایی به آنها اختصاص داده می‌شود، همچنین کانال‌های ارتباطی بین ذرات درنظر گرفته می‌شود. سپس این ذرات در فضای پاسخ حرکت می‌کنند، و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازهٔ زمانی محاسبه می‌شود.

با گذشت زمان، ذره‌ها به سمت ذره‌هایی که دارای سنجه شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب می‌گیرند. مزیت اصلی این روش بر راهبردهای بهینهسازی دیگر، این است که شمار فراوان ذرات ازدحام کننده، سبب نرمش پذیری و انعطاف روش در برابر مشکل پاسخ بهینه محلی (local optimum) می‌گردد.

بهینه‌سازی ازدحام ذراتبهینه‌سازی ازدحام ذرات

سامانه ایمنی ساختگی (هُنردادار)

این روش (به انگلیسی: Artificial Immune System) از سامانه ایمنی پرهامی (طبیعی) برگرفته شده و با مدل کردن برخی یاخته‌های این سامانه می‌کوشد تا از اینگونه سامانه‌ها در راستای بهینه‌سازی یا یادگیری دستگاه (Machine Learning) بهره بگیرد.

الگوریتمهای بر پایه زنبور

چندین الگوریتم در زمینه الگوبرداری از رفتار گروهی زنبورها در کندو یا بیرون آن به ویژه رفتار آنها در خوراکجویی (foraging) برای بهینه‌سازی پیوسته (continuous optimization) پیشنهاد شده‌اند.

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

الگوریتم چکه آب‌های هوشمند

الگوریتم چکه آبهای هوشمند بر پایه بررسی رفتار گروهی چکه‌های آب در رودخانه‌ها برای بهینه‌سازی پیشنهاد شده است. این الگوریتم با گسیل کردن چکه‌های هوشمند آب بر روی گراف مسئله (پرسمان)، می‌کوشد راه‌های بهینه تر را برای گذر چکه‌های یاد شده هموارتر گرداند.

الگوریتم چکه آب های هوشمند

کاربردها

گیرایی هوش ازدحامی در فناوری اطلاعات

همگونی‌هایی بین مسائل متفاوت در حوزهٔ فناوری اطلاعات و رفتارهای حشرات اجتماعی وجود دارد:

  • سامانه‌ای توزیع شده از کنشگرهای مستقل و تعامل کننده.
  • اهداف: بهینه‌سازی کارآیی و توان.
  • خود تنظیم بودن در روش‌های کنترل و همکاری به شکل نامتمرکز.
  • توزیع کار و اختصاص وظایف به شکل توزیع شده.
  • تعاملات غیر مستقیم.

گامهای طراحی یک سامانه

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

  • شناسایی همسانی‌ها: در سامانه‌های IT و طبیعت.
  • فهم: مدلسازی رایانه‌ای روش گروهی طبیعی به شکل واقع‌گرا.
  • مهندسی: ساده‌سازی مدل و تنظیم آن برای کاربردهای IT.

کاربردهای کنونی و آینده

  • مسیریابی در شبکه.
  • سامانه‌های توزیع‌شدهٔ رایانامهای.
  • اختصاص منابع به شکل بهینه.
  • زمان‌بندی وظایف.
  • بهینه‌سازی ترکیبیاتی.
  • روباتیک:
    • بررسی سیستم‌های لوله‌کشی.
    • تعمیرات و نگهداری ماهواره‌ها و کشتی‌ها.
    • روبوت‌های خود-مونتاژ.

منبع

مطالب مرتبط:

الگوریتم کلونی زنبور عسل مصنوعی Artificial Bee Colony (ABC) Algorithm

مقاله های الگوریتم کلونی زنبور عسل( Artificial Bee Colony (ABC) Algorithm) و کاربردهای آن

/0 دیدگاه /توسط

الگوریتم کلونی مورچه ها قسمت 3

مقدمه :

استفاده از الگوریتم‌های ابتکاری در  حل مسئله بهینه‌سازی امری ضروری و اجتناب‌ناپذیر است. این روش از توانایی مورچه‌ها در پیدا  کردن کوتاه‌ترین مسیر بین لانه و یک منبع غذایی الهام گرفته است. وقتی مورچه‌ها در محیط  اطراف حرکت می‌نمایند، اثری شیمیایی به نام فرومون از خود بجای می‌گذارند. وقتی  جمعیتی از مورچه‌ها از چند مسیر بین لانه و یک منبع غذایی حرکت می‌کنند، پس از  مدت زمان معینی مشاهده می‌شود که در مسیرهای متفاوت، فرومونهای برجای گذاشته شده  متفاوت می‌باشد. این امر ناشی از این واقعیت است که مورچه‌هایی که در  مسیر کوتاه حرکت می‌کنند، به علت کوتاه‌تر بودن مسیر در یک مدت زمان معین‌تردد بیشتری داشته‌اند چون مورچه‌ها، مسیر کوتاه‌تر را انتخاب  کرده‌اند. با  استفاده از روش مورچه‌ها، روش جستجوئی پیاده‌سازی می‌شود که در هر مرحله‌ای از اطلاعات مراحل قبلی برای رسیدن به  هدف استفاده میگردد.

تاریخچه الگوریتم کلونی مورچه ها :

به‌کارگیری سیستم مورچگان اولین بار (الگوریتم مورچگان) توسط Dorgio و همکاران . به عنوان یک نگرش با چندین عامل برای حل مسائل بهینه‌سازی ترکیبی یا راه‌حل چندعامله (multi Agent) مشکل، مانند مسئله فروشنده دوره گرد یا (TSP) (Traveling Sales Person)  و مسئله تخصیص منابع یا QAP پیشنهاد و ارائه شد.

الگوریتم بهینه سازی کلونی مورچه ها یا Ant Colony

Optimization و یا به اختصار ACO، که در سال 1992 توسط مارکو دوریگو  و در رساله دکتری وی مطرح شد، یکی از بارزترین نمونه ها برای روش   های هوش جمعی است. این الگوریتم از روی رفتار جمعی مورچه ها الهام گرفته شده   است. مورچه ها با همکاری یکدیگر، کوتاه ترین مسیر را میان لانه و منابع غذایی   پیدا می کنند تا بتوانند در کمترین زمان مواد غذایی را به لانه منتقل کنند. هر   کدام از مورچه ها، به تنهایی قادر به انجام چنین کاری نیستند

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

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

1. اجتماعی بودن:

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

1. باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه‌های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر(بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر.

2. اگر فرومون اصلاً تبخیر نمی‌شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند.

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

2.هوشمندی توده‌ای: هوش جمعی (swarmIntelligence)

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

مورچه ها چگونه کوتاهترین مسیر را انتخاب می‌کنند؟

مورچه ها هنگام راه رفتن از خود ردی از ماده شیمیایی فرومون (pheromone) بجای می‌گذارند که البته این ماده بزودی تبخیر می‌شود ولی در کوتاه مدت بعنوان رد مورچه بر سطح زمین باقی می‌ماند. یک رفتار پایه‌ای ساده در مورچه ها وجود دارد.آنها هنگام انتخاب بین دو مسیر بصورت احتمالاتی (statistical) مسیری را انتخاب می‌کنند که فرومون بیشتری داشته باشد یا بعبارت دیگر مورچه هایبیشتری قبلاً از آن جا عبور کرده باشند.

مسیریابی با الهام از کلونی مورچه ها

  • ترشح اسید فرمیک در مسیر حرکت
  • دنبال کردن مسیرهای با اسید فرمیک بیشتر
  • تبخیر

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

  •   Stigmergy  :  ایده اصلی در تعاملات ارتباط با واسطه محیط  لانه سازی موریانه ها  ترشح اسید فرمیک توسط مورچه هامزایایی که هوش جمعی از آن بهره می برند
  • مقیاس پذیری(scalability): تعاملات توزیع شده موجودات
  • خطا پذیری(Fault tolerance)
  • عدم وجود کنترل متمرکز
  • قابلیت تطبیق پذیری عاملها
  • سرعت انتقال تغییر
  • تفکیک پذیری (modularity)
  • خودکار بودن سیستم : نیاز به نظارت انسان نیست
  • کارکرد موازی

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

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

ویژگیهای الگوریتم کلونی مورچه ها:

الگوریتم مورچگان:

1. چندمنظوره میباشد: می‌تواند برای انواع مشابه یک مسأله به کار رود.

2. قوی می باشد:یعنی با کمترین تغییرات برای دیگر مسائل بهینه‌سازی ترکیبی به کار برده می‌شود

3.یک روش مبتنی بر جمعیت می‌باشد.

 مزیت های ACO :

1. ایجاد انعطاف در حل هرگونه مسئله بهینه‌سازی

2. پسخورد مثبت (پسخورد مثبت، منجر به کشف سریع جوابهاب خوب می‌شود)

3. محاسبات توزیع شده (محاسبات توزیع شده از همگرایی زودرس وبی‌موقع جلوگیری می‌کند)

4. هیوریستیک آزمند سازنده (به کشف جوابهای قابل قبول در مراحل اولیه جستجو کمک می‌کند).

کاربردهای الگوریتم کلونی مورچه ها:

از کاربردهای الگوریتم (ACO) می‌توان به بهینه کردن هر مسئله‌ای که نیاز به یافتن کوتاهترین مسیر دارد استفاده می شود:

  • مسیریابی داخل شهری و بین شهری
  • مسیریابی بین پست‌های شبکه‌های توزیع برق ولتاژ بالا
  • مسیریابی شبکه‌های کامپیوتری
  • مسیر یابی تامین مواد اولیه جهت تولید به هنگام
  • برنامه ریزی دروس دانشگاهی
  • توازن بار ترافیک شبکه ومسیریابی مبتنی برمهندسی ترافیک
  • کاوش استفاده از وب با استفاده از کلونی مورچه ها
  • مسئله زمان بندی حرکت قطار ها
  • برنامه ریزی پرواز
  • بهینه سازی سکوهای دریا
  • مسیریابی شبکه های کامپیوتری
  • مسأله راهیابی در شبکه های مخابرات راه دور

 

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

پروسه پیدا کردن کوتاه‌ترین مسیر توسط مورچه ها، ویژگی‌های بسیار جالبی دارد، اول از همه قابلیت تعمیم زیاد و خود- سازمانده بودن آن است. در ضمن هیچ مکانیزم کنترل مرکزی ای وجود ندارد. ویژگی دوم قدرت زیاد آن است. سیستم شامل تعداد زیادی از عواملی است که به تنهایی بی اهمیت هستند بنابراین حتی تلفات یک عامل مهم، تاثیر زیادی روی کارآیی سیستم ندارد. سومین ویژگی این است که، پروسه یک فرآیند تطبیقی است. از آنجا که رفتار هیچ کدام از مورچه ها معین نیست و تعدادی از مورچه ها همچنان مسیر طولانی تر را انتخاب میکنند، سیستم می تواند خود را با تغییرات محیط منطبق کند و ویژگی آخر اینکه این پروسه قابل توسعه است و می تواند به اندازهٔ دلخواه بزرگ شود.
همین ویژگی‌ها الهام بخش طراحی الگوریتم هایی شده اند که در مسائلی که نیازمند این ویژگی‌ها هستند کاربرد دارند. اولین الگوریتمی که بر این اساس معرفی شد،الگوریتم ABC بود. چند نمونه دیگر از این الگوریتم‌ها عبارتند از: Ant Net،ARA،PERA، Ant Hot Net

نرم‌افزارهای کاربردی در الگوریتم کلونی مورچه ها:

 در برنامه‌های کامپیوتری الگوریتم از زبان برنامه‌نویسی  (Borland C ++5.02,C) نیز استفاده می‌شود مدلهای ریاضی که دراین الگوریتم استفاده می‌شود جوابهای آن بااستفاده از نرم‌افزار LINGO بدست می‌آید.

جمع‌بندی و نتیجه‌گیری:

روشهای بهینه‌یابی موجود برای حل مسائل سخت که بطور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می‌باشند که از کارآیی عملی آنها در حل مسائل با ابعاد واقعی می‌کاهد. بدین علت از الگوریتمهای ابتکاری و فوق ابتکاری هیوریستیک بر مبنای بهینه‌یابی کلنی مورچگان استفاده نمود.استفاده از الگوریتم لانه مورچه و اقتباس از آن در صنعت برای یافتن کوتاهترین مسیر جهت تأمین بهنگام مواد و قطعات باعث کاهش هزینه‌های تولید و انبارداری و بهبود بهره‌وری می‌شود . می توان از روی این الگوریتم برای مسائل چندین عامله نمونه سازی کرد ولااقل به جوابی در حد بهینه و در کمترین زمان یافت.

منبع

منابع

http://fa.wikipedia.org

http://www.asriran.com

http://www.radoo.ir/

http://rayanehmag.net

http://farhanian.blogsky.com

الگوریتم کلونی مورچه ها قسمت 1
الگوریتم کلونی مورچه ها قسمت 2
الگوریتم کلونی مورچه ها قسمت 3

/0 دیدگاه /توسط

الگوریتم کلونی مورچه ها قسمت 2

الگوریتم کلونی مورچگان در رتبه دوم پر اهمیت‌ترین الگوریتم‌ها، در دسته الگوریتم‌های تکاملی قرار می‌گیرد. رفتار بیولوژیکی مورچه برای پیدا کردن غذا نقطه شروع شبیه سازی مصنوعی ما است.

الگوریتم‌های تکاملی یک جهش در زمینه هوش مصنوعی به حساب می‌آید. الگوریتم ژنتیک، اولین الگوریتم تکاملی ارائه شده بود. ژنتیک در کنار قدیمی‌ترین بودن همچنان به عنوان پیشتاز تکامل نیز به حساب می‌آید.

الگوریتم کلونی مورچگان یا (ACO) در رتبه دوم از نظر مصرف قرار دارد. بهتر است ساختار آن را با تشریح مدل بیولوژیکی آغاز کنیم.

مورچه‌ها به مانند پرندگان، زنبور عسل و .. برای پیدا کردن غذا به صورت گروهی حرکت می‌کنند. اصطلاحا به این نوع رفتار هوش جمعی گفته می‌شود. هوش جمعی به این منظور است که تمام تصمیمات مسیریابی و جمع آوری آذوقه از یک مورچه به مورچه دیگر انتقال پیدا می‌کند. تعداد مورچه‌ها در یک کلونی می‌تواند به 30 میلیون برسد!! و هدف تک تک اعضای آن به بقای کلونی باز ‌می‌گردد. غیر از پیدا کردن غذا، تقسیم کار، ساماندهی گورستان و مراقبت از فرزندان نیز در بین کلونی مورچگان مبحثی رایج است.

رفتار جستجو گرانه مورچه‌ها

جالب است بدانید که مورچه‌ها موجوداتی کور، بی‌حافظه و بسیار کم هوش هستند. ولی با این حال همیشه بهینه‌ترین و کوتاه‌ترین مسیر از لانه تا محل غذا را پیدا می‌کنند. ارتباط این مورچه‌ها با یکدیگر از طریق ماده شیمیایی فرومون است. زمانی که مورچه از یک مسیر حرکت می‌کند بر روی زمین فرومون ترشح می‌کند و این باعث می‌شود که مورچه‌های بعدی به دنبال او حرکت کنند. فرومون ها دارای غلظت هستند که طی واحد زمان تبخیر می‌شوند، پس هر چه غلظت فرومون بیشتر باشد مورچه می‌فهمد که این مسیر جدیدتر است. به نحوی می‌توان این غلظت را به عنوان یک فیدبک در نظر گرفت که هر چه غلیظ‌تر باشد امتیاز بالاتری دارد.

حال با توضیحات بالا یک سوال مهم پیش می‌آید: فرض کنید یک مورچه که به عنوان اولین مورچه است، در مسیری حرکت کرده و بقیه مورچه‌ها نیز به دنبال او راه افتاده‌اند. اگر در مسیر حرکت آن غذا پیدا نشود، آن زمان تصمیم چیست؟ طبق این فرضیه هیچ وقت مسیرهای جدید اکتشاف نمی‌شوند و حرکت به یک حلقه بدون پایان تبدیل می‌شود.!

شاید جالب باشد بدانید که بعضی از مورچه‌ها در واقع جوانان اکتشاف‌گری هستند که توجهی به میزان فرومون نمی‌کنند و اهمیتی برای‌شان ندارد که دیگران از چه مسیری رفتند. البته شاید این اتفاق ناشی از هوش کم‌شان باشد.

 

الگوريتم های بهینه سازی کلونی مورچگان

تفاوت مورچه‌های واقعی و مورچه‌های مصنوعی

  • حالت درونی: حافظه‌ای از فعاليت های قبلی مورچه‌ها  (در صورتی که در مورچه‌های واقعی این نوع حافظه وجود ندارد).
  • فرومون مصنوعی: تابعي از کيفيت پاسخ پيدا شده.
  • موانع مصنوعی: تغییر دادن جزئیات مسئله برای بررسی الگوریتم و رسیدن به جواب‌های متنوع.
  • حیات در محیط گسسته: مورچه‌های واقعی نمی‌توانند جدا از  کلونی به حیات خود ادامه دهند.

مدل تصادفی:

احتمال اینکه مورچه بعدی مسیر A را انتخاب کند:

 

 

 

nA(t) و nB(t) تعداد مورچه هایی که در زمان t در مسیر A و B قرار دارند.

c: درجه جذب برای یک مسیر ناشناخته هر چه c بزرگتر باشد به معنی مقدار فرومون بیشتر برای عدم انتخاب مسیر تصادفی است.

a: بایاس به سمت فرومون به جا مانده در روند تصمیم گیری.

ساختار کلی الگوریتم کلونی مورچگان را باهم بررسی کردیم. در طی چند سال گذشته بهینه‌سازی‌های زیادی بر روی این الگوریتم انجام شد، که از انواع آن‌ها می‌توان به الگوریتم‌های زیر اشاره کرد:

SACO: Simple Ant Colony Optimization

ACOA: Ant Colony Optimization Algorithms

AS: Ant System

Elitist AS: Elitist Ant System

ACS: Ant Colony System

Max-Min AS

و …

منبع

الگوریتم کلونی مورچه ها در هوش مصنوعی

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

بهینه سازی کلونی مورچه ها یا Ant Colony Optimization و به اختصار (ACO)، که در سال ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) و در رساله دکتری وی مطرح شد، یکی از بارزترین نمونه ها برای روش های هوش جمعی است. این الگوریتم از روی رفتار جمعی مورچه ها الهام گرفته شده است. مورچه ها با همکاری یکدیگر، کوتاه ترین مسیر را میان لانه و منابع غذایی پیدا می کنند تا بتوانند در کمترین زمان مواد غذایی را به لانه منتقل کنند. هیچ کدام از مورچه ها، به تنهایی قادر به انجام چنین کاری نیستند، اما با همکاری و پیروی از چند اصل ساده، بهترین راه را پیدا می کنند. الگوریتم مورچه ها، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندان بالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند.

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

برای هر مورچه کارهای زیر باید انجام شود:

۱- قانون حرکت احتمالی: براساس این قانون مورچه را در فضای جستجو حرکت داده به این ترتیب راه حل مسئله ایجاد می شود
۲- ارزیابی بهترین: باید بهترین راه حلی که توسط این مورچه ایجاد شده را ارزیابی کرد
۳- به روز کردن فرمن: فرمن هر ضلع را با استفاده از تقویت یک راه حل خوب به روز می کنیم
۴-  دوباره به مرحله دوم برگشته و این کار را ادامه می دهیم تا به میزان فرمن دلخواه برسیم
يک رفتار پايه اي ساده در مورچه ها وجود دارد : آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي (Statistical) مسيري را انتخاب مي کنند که فرمن بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري  قبلا از آن عبور کرده باشند. حال می بینیم که همين تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :
همانطور که در شکل مي بينيم مورچه ها روي مسير در حرکت اند (در دو جهت مخالف)
اگر در مسير مورچه ها مانعي قرار دهیم مورچه ها دو راه براي انتخاب کردن دارند.
اولين مورچه از A مي آيد و به C مي رسد، در مسير هيچ فرمني نمي بيند بنابراين براي مسير چپ و راست احتمال يکسان مي دهد و بطورتصادفي و احتمالاتي مسير CED  را انتخاب مي کند.
مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرمن را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا)  انتخاب مي کنند. در نهايت مسير CED  بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED  کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرمن بيشتري در آن وجود دارد.
نکته ديگر مسئله تبخير شدن فرمن بر جاي گذاشته شده است. برفرض اگر مانع در مسيرAB  برداشته شود و فرمن تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرمن و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند. تبخیر فرمون از ۳ جهت مفید است:

۱) باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در بلند مدت راه های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر(بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر،

۲) اگر فرمن اصلاً تبخیر نمی شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند،

۳) وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.

حل مسئله ی فروشنده دوره گرد با الگوریتم کلونی مورچه ها

همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گردTSP)) ، در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. برای حل مسئله فروشنده سیار که باید از n شهر دیدن کند و از هر کدام فقط یکبار عبورکند نیز می توان از الگوریتم ACO استفاده کرد. مثلا اگر زوج مرتب (N,E) را در نظر بگیریم که N تعداد شهرها و E اضلاع گراف باشند و di,j فاصله اقلیدسی بین شهرهای i و j باشد و  b تعداد مورچه ها در شهر i و در زمان t، هریک از مورچه ها باید مراحل زیر را انجام دهد:

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

کاربردهای الگوریتم کلونی مورچه ها

از کاربردهايACO  مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود مانند :
۱٫ مسير يابي داخل شهري و بين شهري
۲٫  مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا
۳٫ مسير يابي شبکه هاي کامپيوتري

برخی از کاربردهای الگوریتم کلونی مورچه ها

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

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

استفاده پژوهشگران از الگوي کلونی مورچه ها جهت اداره ترافيک

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

حل مسائل زمانبندي پروژه ها با منابع محدود با استفاده از الگوريتم مورچگان

مساله زمانبندي پروژه ها با منابع محدود (RCPSP) درگير يافتن توالي مناسبي براي انجام فعاليتهاي يك پروژه است به نحوي كه محدوديت هاي تقدم و و تاخر شبكه پروژه و انواع مختلف محدوديتهاي منبعي موجود در پروژه به طور همزمان ارضاء شوند و معيار سنجش معيني از جمله زمان انجام پروژه، هزينه انجام، تعداد فعاليتهاي تاخيردار و غيره بهينه گردند. RCPSP  مساله اي NP-hard به شمار مي آيد و اهميت اين مساله در ابعاد تئوري و عملي باعث شده است كه تاكنون رويكردهاي ابتكاري و يا فراابتكاري جهت حل اين مساله ارائه شود. رويكردي بر اساس بهينه سازي توسط كلوني مورچگان براي حل مساله زمانبندي پروژه ها با منابع محدود ارائه شده است . از جمله تفاوتهاي اصلي رويكرد ارائه شده  با این شیوه قانون انتخاب احتمالات به صورت نوين، تغيير پارامترهاي الگوريتم به صورت پويا، جلوگيري از بروز رفتارهاي نامناسب الگوريتم در تكرارهاي بالا و تعيين رفتار كلي الگوريتم در تكرارهاي بالا می باشد.

كاربرد الگوريتم مورچه در بهينه سازي شبكه هاي توزيع آب

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

الگوريتم مورچه اي براي طراحي مسير حركت باربران خودكار در سيستم تك حلقه

در این کاربرد هدف تعیین کوتاه ترین حلقه برای یک بابر خودکار در چیدمان کارخانه به نحوی است که با هر دپارتمان لااقل یک ضلع مشترک داشته باشد. برای این منظور در ابتدا با استفاده از خواص مسئله آن را به مسئله ای معادل نظریه گراف تبدیل کرده و سپس با به کارگیری الگوریتم کلونی مورچه ها مسئله حل شده است. در روش های مسیریابی سیستم تک حلقه این روش به خوبی عمل کرده است.

استفاده از الگوريتمaco  درطراحي شبكه هاي توزيع شعاعي

در اینجا از الگوريتم کلونی مورچه ها در طراحي بهينه شبكه هاي توزيع شعاعي كه در آنها مسير تغذيه مشخص است، استفاده مي شود. اين الگوريتم ضمن ارائه ميزان نفوذ هر يك از سطوح ولتاژ در شبكه مورد مطالعه، ظرفيت بهينه ترانسفورماتور ها و سطح مقطع بهينه فيدرها را در هر يك از سطوح ولتاژي ارائه مي نمايد. الگوريتم فوق بر روي يك شبكه نمونه اجرا شده و نتايج آن نشانه برتري روش ارائه شده نسبت به روش الگوريتم pso و الگوريتم سطح تغذيه است. نقطه قوت اين الگوريتم سرعت بالا، يعني بيشتر از ۲۴۰ برابر الگوريتم تعيين سطح تغذيه و بيش از ۱۸ برابر الگوريتم pso و همچنين كاهش۱۰ درصدي (بطور متوسط) قيمت نهايي در مقايسه با ديگر الگوريتم هاي موجود به سبب اضافه كردن ظرفيت ترانسفورماتور ها به عنوان متغير فضاي جستجو مي باشد.

ارايه يک مدل ابتکاري مبتني بر سيستم اجتماع مورچه ها براي حل مسئله زمان بندي حركت قطار

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

بررسی پارامترهای الگوریتم AntNet

تنوع زیادی در پروتکلها و الگوریتم های مسیریابی برای ارتباطات شبکه ای وجود دارد. در مسیریابی سنتی جداول مسیریابی به واسطه تبادل اطلاعات مسیریابی بین مسیریابها به روز می شوند. الگوریتم هایی که با الهام از کلونی مورچه ها ارائه شده از عاملهای موبایل در مسیریابی شبکه ها استفاده می کنند. در این الگوریتم ها مسیریابی بصورت hop by hop و بر اساس خاصیت stigmergic در کلونی مورچه ها انجام می شود. stigmergicشکلی از ارتباط غیر مستقیم است که به وسیله تاثیر روی محیط انجام می شود. به این صورت که عامل ها (مورچه ها) در شبکه حرکت می کنند و جداول مسیر یابی را به روز می کنند.
منبع

الگوریتم کلونی مورچه ها قسمت 1
الگوریتم کلونی مورچه ها قسمت 2
الگوریتم کلونی مورچه ها قسمت 3

/0 دیدگاه /توسط

هوش محاسباتی

هوش محاسباتی شاخه‌ای از هوش مصنوعی است که در آن از الگوریتم‌هایی مانند شبکه‌های عصبی، محاسبات تکاملی و سیستم‌های فازی استفاده می‌شود.

منبع

انسان موجود کاملی نیست و به همین دلیل همواره نیازهای فراوانی در زندگی وی ظاهر می‌شوند. این نیازها در ادوار مختلف تمدن بشری، از نظر نوع و شدت، تغییرات فراوانی داشته‌اند. در بسیاری از مواقع، نیازهای دو نسل پیاپی از انسان‌ها، تفات‌های بسیاری با هم دارند و مسائلی برای افراد یک نسل اهمیت دارند که نسل پیشین یا پسین، کاملا نسبت به آن مسائل، بی توجه هستند. اما چیزی که در میان تمام نسل‌های بشری مشترک است، تلاش برای رفع نیازها و کمبودهای ذاتی است.علی رغم کمبودها و نیازهای بسیاری که همراه انسان هستند، قدرت تفکر و نوآوری انسان، این امکان را به او می‌دهد که بتواند با ابداع و اختراع، بخش قابل توجهی از محدودیت‌ها و نیازهایش را جبران کند.
انسان از نظر توان فیزیکی، موجودی محدود است. در میان جاندارانی که در خشکی، دریا و هوا حرکت می‌کنند؛ انسان جایگاه قابل توجهی ندارد. سرعت حرکت انسان در خشکی و آب،کاملا محدود است. اقامت انسان در زیر آب فقط محدود به مدت زمان کوتاهی بوده و پرواز در آسمان نیز برای انسان غیر ممکن است. انسان قدرت بلند کردن هر وزنه‌ای را ندارد. با درک چنین نیازهایی، در طول قرون و اعصار مختلف، اختراعاتی چون: هواپیما، کشتی، چاقو، جرثقیل، لباس و تجهیزات غواصی و طناب اختراع شده‌اند. تمامی اختراعات یاد شده، در جهت رفع محدودیت‌های فیزیکی انسان‌ها ایجاد شده‌اند.
پس از مدتی که تمدن نوپای بشری کار خود را آغاز نمود، نوع دیگری از نیازها برای انسان مطرح شدند. نیازهایی که در مقایسه با نیازهای فیزیکی، قدری لوکس‌تر به نظر می‌رسند. انسان در این مرحله، علاقه‌مند به ثبت وقایع و دستاوردهای خود شد. نقاشی‌هایی که امروزه در غارها کشف می‌شوند و سنگ‌نوشته‌ها و کتیبه‌هایی که در موزه‌های مختلف وجود دارند نشان از علاقه‌مندی بشر، به حفظ و انتقال اطلاعات دارد. نیاز به ذخیره‌سازی و تبادل اطلاعات، در زمان‌های مختلف توسط بشر حس شده است و اختراعات و ابداعاتی از قبیل دیسک‌های نوری، دوربین عکاسی، خط، تلفن، کبوتر نامه‌بر، و اینترنت، همگی محصول توجه به این نیاز بوده‌اند.
دسته‌ی دیگری از محدودیت‌هایی که انسان رفته رفته بیشتر با آن‌ها روبرو شد، و سعی در رفع آن‌ها نمود، شامل خستگی، محدودیت سرعت کار، و عدم مصونیت از خطا است. به عنوان مثال، محاسبات سنگین و حجیم، حتی اگر توسط انسان قابل انجام هم باشد؛ قطعا مصون از خطا و اشتباه نخواهد بود. انسان نمی‌تواند یک طرح را صدها بار بدون هیچ تفاوت (حتی جزئی) اجرا نماید. ساعات کار مفید انسان، در هر کاری که باشد، کاملا محدود و متاثر از محدودیت‌های فیزیکی اوست. به خصوص اگر ماهیت کار به نوعی باشد که با قوای فکری و محاسباتی انسان مرتبط باشد. قطعا با طولانی‌تر شدن زمان کار، کیفیت کار نیز خدشه‌دار خواهد شد. این نوع از نیازها و محدودیت‌ها منجر به ایجاد اختراعاتی چود ساعت، چاپگر، و کامپیوتر شدند. این اختراعات، مجموعه‌ای از کارها (احتمالا تکراری) را بدون هیچ خستگی یا خطایی انجام می‌دهند.
بشر امروز، علاوه بر نیازهای فیزیکی، ثبت و انتقال اطلاعات و پردازش دقیق نوع دیگری از نیاز را تجربه می‌کند. نیازی که تا 50 سال پیش، هیچ گاه به صورت جدی برای انسان مطرح نشده بود. تا پیش از این، انسان در پی ایجاد ابزارهایی بود که به جای او: کارهای فیزیکی انجام دهند، اطلاعات را به یاد داشته باشند (و منتقل کنند) و به جای او محاسبه کنند! اما امروزه انسان در پی ایجاد ابزارها و ادواتی است که به جای او فکر کنند، یاد بگیرند و تصمیم گیری کنند. ابزارهایی که از قدرت تحلیل و هوش انسان تقلید می‌کنند. به این ترتیب بود که هوش مصنوعی (Artificial Intelligence) به عنوان یکی از نیازهای عصر جدید مورد توجه انسان‌ها قرار گرفت.
فرض کنید که به جای استفاده از یک هوش انسانی در زمینه کنترل امنیت یک سازمان یا اداره، از سیستمی استفاده شود که قدرت تشخیص اثر انگشت، چهره و صدای افراد را دارد و می‌تواند تمام افراد وارد شونده یا خارج شونده را شناسایی نماید. این کاربرد نمونه، نیازمند استفاده از چندین تخصص از رشته‌های مختلف علمی و مهندسی است که اصلی‌ترین مورد در میان آن‌ها، بحث هوش مصنوعی می باشد. سیستم‌هایی همچون خلبان خودکار در هواپیما، کنترل کننده‌های ترافیک شهری، ادوات مراقبت پزشکی هوشمند، ابزارهای تبدیل صوت به متن و روبات‌های هوشمند، از جمله مظاهر استفاده از هوش مصنوعی در زندگی روزمره هستند.
هوش مصنوعی از جمله مباحثی است که تا پیش از اختراع کامپیوترها صحبت کردن در مورد آن‌ها عملا غیر ممکن بود. پس از ورود کامپیوترها به زندگی بشری بود که بحث در خصوص هوش مصنوعی به یکی از مباحث داغ تبدیل شد. هوش مصنوعی از نظر علمی، بخشی از علوم کامپیوتر است و امروزه به عنوان مبحثی اساسی و کاربردی در رشته‌های مختلف علوم پایه و مهندسی مورد مطالعه و پژوهش قرار می‌گیرد. اطلاعات بیشتر درباره آن را می توانید در این دو بخش (1 – 2) بخوانید.

هوش محاسباتی (Computational Intelligence)

یکی از زیر بخش‌های بسیار مهم و کاربردی هوش مصنوعی است، که در آن از ابزارهای مختلفی برای تحقق ایده‌ی هوش مصنوعی استفاده می‌شود. ابزارهای مورد استفاده در هوش محاسباتی، غالبا ابزارهایی ریاضی هستند که به نوعی از طبیعت و دنیای اطراف الهام گرفته شده‌اند. مهم‌ترین ابزارها و الگوهایی که در هوش محاسباتی مطرح می‌شوند، شامل موارد زیر هستند:

محاسبات تکاملی (Evolutionary Computation)

محاسبات تکاملی شامل مجموعه‌ای از روش‌ها است که به نام الگوریتم‌های تکاملی معروف هستند. مشهورترین این الگوریتم‌ها الگوریتم ژنتیک است که از نظریه تکامل و علم ژنتیک الهام گرفته شده است. در این الگوریتم، فرآیند تکامل، که طی میلیون‌ها سال در طبیعت اتفاق افتاده است، شبیه‌سازی می‌شود. اصلی‌ترین مورد کاربرد الگوریتم‌های تکاملی، حل مسائل بهینه‌سازی و برنامه ریزی ریاضی است.

هوش ازدحامی (Swarm Intelligence)

روش‌هایی که در این دسته قرار می‌گیرند، الگوی دیگری را برای حل مسائل بهینه‌سازی پیشنهاد می‌کنند. در این روش‌ها، تعداد قابل توجهی از عامل‌های بسیار ساده و کم هوش، برای تشکیل نوعی هوش ازدحامی یا هوش جمعی با یکدیگر همکاری یا رقابت می‌کنند. به عنوان مثال، الگوریتم بهینه‌سازی مورچگان، که از رفتار جمعی مورچه‌ها الهام گرفته شده است، یکی از الگوریتم‌های هوش ازدحامی است.
  

شبکه‌های عصبی مصنوعی (Artificial Neural Networks)

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

سیستم‌های فازی (Fuzzy Systems)

نظریه‌ی مجموعه‌های فازی و محاسبات فازی از ابداعات پرفسور لطفی عسگرزاده، استاد ایرانی-آذربایجانی دانشگاه برکلی آمریکا است. در محاسبات فازی، به جای استفاده از اعداد دقیق برای توصیف یک مفهوم، از کلماتی مانند کم یا زیاد استفاده می‌شود. به عنوان مثال در عبارتی مانند سود زیاد دقیقا مشخص نشده است که چه مقدار سود چقدر است. سیستم‌هایی که در آن‌ها به جای نظریه کلاسیک مجموعه‌ها و محاسبات کلاسیک ریاضی، از نظریه مجموعه‌های فازی و محاسبات فازی بهره گرفته می‌شود، به نام سیستم‌های فازی شناخته می‌شوند. امروزه از سیستم‌های فازی در طراحی سیستم‌های مختلف، از جمله لوازم خانگی هوشمند، استفاده‌های فراوانی می‌شود.
در کنار موارد یاد شده، ابزارهای ریاضی دیگری نیز به کار گرفته می‌شوند تا عملکرد کلی سیستم‌های مبتنی بر هوش محاسباتی بهبود یابند. هدف اصلی محققین حوزه‌های هوش مصنوعی و هوش محاسباتی، ایجاد ابزار آلاتی است که ما را به ایجاد هوش مصنوعی هم تزار با هوش انسانی نزدیک‌تر نماید.
/0 دیدگاه /توسط