چمران-الكترو كامپ

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

6 – الگوریتم اجتماع مورچه (Ant Colony Algorithm)

 6-1- معرفی

یکی از مسائلی که به­وسیله­ی زیست­شنا­سان مورد مطالعه قرار گرفته است درك این موضوع است که چگونه موجودات تقریبا کور مانند مورچه­ها کوتاه­ترین مسیر را از لانه­ی خود تا منبع غذا و بر عکس پیدا می­کنند.آن­ها پی بردند که یک رسانه براي ابلاغ اطلاعات بین تک­تک مورچه­ها مورد استفاده قرار می­گیرد و براي تصمیم­گیري درمورد این­که کدام مسیر را انتخاب کنند به­کار می­رود که آن رسانه عبارت است از بو(اثر) ماده­اي به­نام فرومون[1].

 الگوریتم­های لانه­ی مورچه از جمله روش­های فرامکاشفه­ای هستند که برای حل مسایل بهینه­سازی سخت پیشنهاد شده­اند. این الگوریتم­ها در آغاز از رفتارهای اجتماعی پشت سرهم قرار گرفتن و تعقیب کردن الهام گرفته شد، که در جامعه­ی مورچگان مشاهده گردید. یک اجتماع از عامل­های[2] ساده (مورچه­ها) به طور غیر مستقیم از طریق تغییرات پویای (دینامیکی) محیط ارتباط برقرار می­کنند (رد پاهایی از فرومون) و بنابراین بر اساس تجربه­ی اجتماعی آن­ها، یک راه­حل برای یک مسئله ارائه می­دهند.

نخستین الگوریتم از این نوع (سامانه­ی مورچه) برای مسئله­ی فروشنده­ی دوره­گرد طراحی شد،  اما نتایجش چندان امیدبخش نبود.  

6-2- ویژگی­های الگوریتم

این الگوریتم داراي ویژگی­هاي زیر است:

·         چند منظوره است، به عبارت دیگر می­تواند براي انواع مشابه یک مسئله به­کار رود.

·         قوي است، یعنی با کمترین تغییرات براي دیگر مسائل بهینه­سازي ترکیبی به کار برده می­شود.

·         روشی مبتنی بر جمعیت است.

6-3- رفتار طبیعی مورچه

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

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

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

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

1. مورچه­هاي مصنوعی مقداري حافظه خواهند داشت،

2. آن­ها کاملا کور نیستند،

3. آن­ها در محیطی زندگی می­کنند که زمان گسسته است.

6-4- سامانه­ی مورچه[3]

در اين بخش سامانه­ی مورچه معرفي می­شود و از مسئله­ی فروشنده­ی دوره­گرد به­عنوان معيار استفاده مي­­گردد. در مسئـله­ی فروشنده­ی دوره­گرد، يك فروشنده سفر خود را از يك شهر آغاز می­کند و پس از يك سفر كامل دوباره به شهر خودش باز مي­گردد و از هر شـهر فـقط يك­بار عبور مي­كند و در ضمن بايد از همه­ی شهرها عبور كند. هدف يافتن كوتاه­ترين مسير براي اين سفر است.

هر مورچه يك نماينده­ی ساده باويژگي­هاي زير است:

1.        يك شهر را براي رفتن انتخاب مي­كند كه تابعي از فاصله­­ی شهر و مقداربوی (اثر) موجود در آن مسير است.

2.        براي واداركردن مورچه­ها جهت انجام سفرهاي منطقي، سفر به شهرهايي كه يك­بار از آن­ها عبوركرده است ممنوع می­شود.

3.     هنگامي كه يك مورچه يك سفركامل انجام مي­دهد مقداري فرمون برروي هرمسير  و  بر جای مي­گذارد.

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

برای این­که شرط تکراری نبودن شهرها و نیز گذشتن از همه­ی آن­ها برقرار گردد، به هر مورچه یک لیست ممنوع نسبت داده می­شود که دارای شهرهای عبور کرده می­باشد.

6-5- بیان الگوریتم

با توجه به تعاريف بخش پیش الگوريتم­ها معرفي مي­شوند. در زمـان صفر يعني مرحله شروع، مورچه­ها درشـهرهاي مختـلف مستقر مي­شوند و ارزش اوليه­ی شدت بو(اثر) بر روي مسيرها تعیین می­گردد. شهر آغازين به عنوان اولين عنصر وارد ليست مي­شود. سپس هرمورچه از شهر  با تابع احتمال   به سمت شهر  حرکت می­کند، كه خود تابعي از دو معيار مطلوبيت است: يكي احتمال اين­كه در گذشته چه تعداد مورچه از مسير رفته­اند، ديگري قابليت رويت[4] كه مي­گويد شهرهاي نزديك براي مورچه­ها مطلوب­تراند.

بعد از  تكرار همه­ی مورچه­ها يك سفر كامل انجام داده­ا­ند وليست ممنوع آ­ن­ها پرشده ا­ست. همچنين كوتـاهترين مسير يافته­شـده به­وسيله­ی مورچه­ها ذخيره شده و ليست­هاي ممنوع خالي مي­شوند. اين فرايند تا زماني كه تعداد سيكل­ها به حداكثر خود برسد يا همه مورچه­ها يك سفر يك­سان انجام دهند ادامه مي­يابد. اين حالت رارفتار ركودي مي­نامند زيرا الگوريتم جستجوي راه­حل­هاي ديگر را متوقف مي­كند.

قابل ذکر است که سه نوع الگوریتم مورچه وجود دارد: 1. چگالی مورچه[5]، 2. تعداد مورچه[6]، 3. دور مورچه[7].

در دو الگوريتم اول مقدار فرمون در پايان هر تكرار تعديل مي­شود. اما در الگوريتم سوم پس از پايان يك دور اين عمل انجام مي­گيرد. پس از انجا­م شدن چند دور فقط به مورچه­اي كه بهترين مسير را مي­پيمايد اجازه ترشح­كردن فرمون داده مي­شود، اين عمـل به منظور جـهت­دار كردن جستجو انجام مي­گيرد يعني با اين كار مورچه­ها در همسايگي بهترين مسـيري كه تاكـنون پیدا شـده است بـه جستـجو مـي­پردازند. دو الگوريتم اول دقيقا مثل هم هستند و فقط از لحاظ تعديل­كردن (به­روزرسانی) فرومون با هم  متفاوت­اند  .

6-6- حالت کلی الگوریتم

الگوریتم اجتماع مورچگان دارای سه بخش اصلی زیر است:

1.        بخش مقداردهی اولیه، که عبارت است از تشکیل گرافی که بر اساس مسئله­ی بهینه­سازی ترکیبی در دست بررسی و پارامترها، با توجه به ارزش­های اولیه­اشان، ساخته می­شود،

2.        بخش ایجاد راه­حل، که در آن هر مورچه راه­حل خودش را برای مسئله تولید می­کند، و تا زمانی که همه­ی مورچه­ها راه­حل خود را کامل کنند ادامه می­یابد،

3.        بخش به­روزرسانی فرومون، که طی آن دنباله­ی فرومون متناظر با هر اتصال در گراف ساختمان بر اساس قانون به روز رسانی، به روز خواهد شد.

6-7- مقایسه با دیگر روش­های فرامکاشفه­ای

الگوریتم کلونی مورچه دارای ویژگی­هایی در مقایسه با دیگر روش­های فرامکاشفه­ای است:

1.        محاسبات گسسته در طبیعت،

2.        فرایند تجزیه­ی واکنش توسط یکی از محصولات خودش[8]،

3.        استفاده از جستجوی حریصانه و اطلاعات اکتشافی سازنده (آگاهانه).

[1] Pheromones

[2] agent

[3] Ant System

[4] Visibility

[5] Ant Density

[6] Ant Quantity

[7] Ant Cycle

[8] Autocatalytic

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

 جستجوی تابو (Tabu Search)

 تاریخچه

جستجوی تابو نخستین بار توسط فرد گلوور[1] در مقاله­ی منتشر شده در سال 1986]گلوور،1986[ بیان شد، البته این مقاله از بسیاری نظریه­های پیشنهادی در گذشته طی دهه­ی 60 استفاده کرده بود. دو مقاله­ای ]گلوور،1989،گلوور،1990[ که عنوان آنها جستجوی تابو بود بسیاری از اصولی را که امروزه شناخته شده­اند، بیان کردند. برخی از این اصول اقبال چندانی را برای مدت طولانی در میان جامعه­ی علمی به­دست نیاورد. در واقع، در نیمه­ی نخست دهه­ی 90، بیشتر کارهای تحقیقاتی در زمینه­ی جستجوی تابو، دامنه­ی کوچکی از اصول این روش[2] را به کار می­گرفت؛ که عموما محدود به یک لیست تابو[3]  و یک شرط تکاملی[4] ساده بود.

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

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

فرایند تصادفی (اتفاقی)(stochastic) = خانواده ای از متغیرهای تصادفی X(t) (مجموعه ی مرتب X(t)) که t پارامتر شاخص (معمولا زمان) است.

گونه های فراوانی از فرایندهای تصادفی موجود است.دو و یژگی متمایز کننده ی فرایند های تصادفی این است که آیا مقادیری که فرایند تصادفی می تواند در سرتاسر برخی بازه ها دریافت کند پیوسته(continuous) هستند یا نه و آیا پارامتر شاخص(index parameter) پیوسته است یا گسسته (discrete).

دسته بندی فرایندهای تصادفی :

برای دیدن ترجمه ی کامل به دنباله ی نوشته بروید.

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

به نام خدا

در سال 1997 تکنولوژی نوینی پدیدار گشت که در سراسر جهان ، دسترسی به صدا و تصاویر دیجیتالی را فراهم کرد که DVD نام داشت و موجب تغییرات اساسی در صنعت فیلم و تصویر شد.

صنعت بازهم آماده ی انقلابی دیگر با معرفی دیسک های بلو – ری(Blu-ray Discs(BD)) در سال 2006  می باشد . با  توانایی ذخیره سازی بالا، دیسک های بلو - ری  قادر به ذخیره و اجرای صدا و ویدیوی با کیفیت بالا(high-definition video and audio) و همچنین عکسها،داده ها و دیگر موارد دیجیتالی هستند.

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

-          بلوری جانشینی برای DVD

-          فرمت های موجود در blu – ray

-          توانایی ذخیره  سازی

-          سرعت خواندن/نوشتن   دیسک های BD

-          بلو – ری از کدام فرمتهای ویدیویی و صوتی پشتیبانی خواهد کرد

-          ساختمان دیسکهای بلو – ری

-          روش های به کار برده شده برای افزایش ظرفیت دیسک های بلو – ری

-          تکنولوژی کتابخانه ای بلو – ری

-          مقایسه ی عملکرد ذخیره سازی بلو – ری و DVD

-          مقایسه ی بلو – ری و HD-DVD

-          فناوری درایو بلو – ری

-          برخی دیگر امتیازات  بلو – ری

-          امنیت  اطلاعات در بلو – ری

-          هزینه ی استفاده برای مصرف کنندگان

-          رقیبان عرصه ی بلو – ری

-          مشکلات رقابت میان بلو – ری و دیگر فرمتها

-          محدودیت های استفاده از امکانات جدیدی که برای بلو – ری ایجاد می شود

-          جدول مقایسه میان ویژگی ها ی بلو – ری و DVD

-          تصاویری از مقایسه میان بلو – ری DVD و HD-DVD

نام مقاله : معرفی فناوری بلو – ری

گرداورنده: وحید محمدی صفارزاده

 در دنباله ی نوشته این مقاله را  برای دانلود گذاشته ام. 

واژگان پایه: Blu-Ray،بلو ری، DVD، BD، HD-DVD، high-definition video and audio، BDA،sony، NA، UDF.

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

به دنباله ی اعداد زیر توجه کنید :

....1،1،2،5،14،42

به نظر شما چه رابطه ای بیانگر این دنباله می باشد...

برای اینکه رابطه ی بین اعداد بالا را درک کنیم از یک مثال جالب بهره می بریم.

مجموعه ای از مسایل وجود دارند که دارای راه حلی کاملا مشابه هستند یعنی جواب همه ی آنها دنباله ای از اعداد موسوم به اعداد کاتالان(Catalan Numbers) می باشد. 

 برای دیدن نمونه ای به دنباله ی نوشته بروید...

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

به نام خدا

الگوریتم رمز گذاری هافمن(Huffman)

روش رمز گذاری هافمن به عنوان بخشی از روشها ی فشرده سازی مانند LZW مورد استفاده قرار می گیرد. و در واقع یکی از روشهای بهینه سازی در ذخیره اطلاعات می باشد. کدهای هافمن در فشرده سازی داده ها بسیار پر کاربرد می باشند.یک تکنیک موثر به حساب می آیند که می توانند 20 تا 90 درصد صرفه جویی را در پی داشته باشند.این الگوریتم به ویژگی های داده هایی که فشرده می شوند بستگی دارد  مثلا دنباله ای از کاراکترها(حروف) .

الگوریتم حریصانه (Greedy) ی هافمن یک جدول برای نمایش حروف  و میزان تکرار آن ها در یک (مثلا فایل ) به دست می دهد تا روش کد گذاری کاراکترها را (به صورت رشته های باینری) به بهترین شکل فراهم سازد .

در این روش تلاش می شود تا از حداقل بیتهای ممکن برای سمبلهایی که بیش از سایر سمبلها تکرار شده اند استفاده شود.مثلا در متنهای انگلیسی ممکن است حرف E متداول ترین حرف باشد .که ما با بهره گیری از این روش می توانیم حرف E را با 2 بیت نمایش دهیم (مثلا10) این ترکیب برای نمایش حرف E در کدهای اسکی به کار می رود. روش اسکی تقریبا برای ذخیره سازی و انتقال بین تمام کامپیوترها مورد استفاده قرار می گیرد.

اساس کار رمز گذاری هافمن در واقع یک الگوریتم است که بر پایه ای استوار است که تعداد تکرار داده ها درون یک فایل همسان نیستند.با این الگوریتم به داده هایی با تعداد تکرار بیشتر کدی  نسبت داده شده و به داده ای با تعداد تکرار (Frequency) کمتر کدهای بلندتر نسبت داده می شود.

برای نمونه :

تعداد تکرار حروف در متنی  به گونه ی زیراست:

الف > 5 تکرار

ب> 6 تکرار

ج> 30 تکرار

در حالت عادی برای نمایش سه داده به دو بیت نیاز است بنابر این حاصل برابر است با 2*(30+6+5)=82

یعنی به 82 بیت نیاز داریم و لی اگر با بهره گیری از الگوریتم کد هافمن به حرف ج (بیشترین بسامد ، تکرار) کد 1 بیتی ، به الف و ب کد 2 بیتی  نسبت داده شود حاصل برابر است با 1*30+2*(6+5)=52 یعنی به 52 بیت نیاز است . حدود 30%  صرفه جویی !

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

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

سلام

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

متن انگلیسیش هم گذاشته شده.

به دنباله ی نوشته بروید...

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

سلام

دراین پست و سری پستهای بانام "اصطلاحات دانش کامپیوتر(Terms Of computer Science)"  این آهنگ را دارم که به بیان اصطلاحات علمی (رایج و غیر رایج) و ترکیبات کوتاه شده و دیگر اصطلاحات رایانه ای بپردازم امیدوارم که برای اهالی دانش سودمند باشد.تلاش می کنم در هر پست   اصطلاحات دو حرف و از هر حرف 10 واژه را گفته ،تا حرف آخر.این کار دوباره از آغاز انجام خواهد شد. البته در صورت در خواست اصطلاحی ویژه جداگانه آن را خواهم گفت.

برای دیدن بخش 1 به دنباله ی نوشته بروید...

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

....

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