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

مساله فروشنده دوره گرد (TSP ) يكي از مسائل مشهور بهينه سازي تركيبي است كه اساس آن به اين صورت است كه يك فروشنده دوره گرد مي خواهد بهN شهر برود و كالاي خود را به فروش برساند ، به طوري كه از هر شهر فقط يك بار عبور كند و تمام شهر ها را رفته باشد و در نهايت كمترين مسير را طي كرده باشد عکس. دراينجا يك ماتريس فاصله شهر ها (d) وجود دارد كه فاصله شهر i از j را با dij نشان می دهد و فاصله شهر i از خودش را با dii نشان مي دهيم كه مقدار آن صفر است و روي قطر اصلي ماتريس مي باشد . يك تور يك جايگشت Π از {n،......1,2,} مي باشد . هدف مساله فروشنده دوره گرد پيدا كردن جايگشتي است كه كمترين طول را دارد. فضاي حل مساله TSP با زياد شدن تعداد شهرها به سرعت افزايش مي باشد و ديگر با روشهاي برنامه ريزي خطي نمي توان جواب بهينه آن را به دست آورد.

بقیه در ادامه ی مطلب ...

ادامه مطلب

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

الگوریتم ژنتیک یا Genetic Algorithm (GA) در واقع شبیه سازی بقای انسان هست! تا حالا پیش خودتون فکر کردین این همه سال گذشته چطوری انسان ها از بین نرفتن و نسلشون پا برجاس؟ فکر می کنید رمز موفقیتشون چیه؟

فکر کنم 183462130973.347928374261010000001 باشه!

" ... "

انسان ها بقا دارن چون با یه قانون خاصی پیش میرن که واضحه که موفق بوده!
حالا همین قانون رو توی کامپیوتر میشه شبیه سازی کرد! اما چجوری؟
فکر کنید میخوایم جواب این تابع رو بدست بیاریم:

كد:

X^2 + e^X + 3*sin(X) + int(-X^X) / X = 12

بنظر خیلی پیچیده میاد! شاید با روش های تحلیلی حل نشه و نیاز به محاسبات عددی باشه! یکی از راه ها الگوریتم ژنتیک هست که بعضی اوقات به شکل باور نکردنی سریع به جواب میرسه.
خوب پس من با یه مقدمه ازش شروع می کنم:

اولین مرحله اینه که ما یک سری کرومزوم به عنوان جمعیت اولیه بصورت تصادف انتخاب می کنیم. هر کرومزوم یه عدد هست در مبنای دو.
مثلا این کرومزوم هارو به عنوان جمعیت اولیه در نظر می گیریم:

كد:

بعد از اینکه جمعیت اولیه معلوم شد این کرومزوم ها توی تابع Fitness امتحان میشن و بر حسب اینکه به جواب مورد نظر نزدیکن یا نه یه عدد بین صفر تا یک بهشون اختصاص داده میشه که صفر یعنی اصلا بدرد نمی خوره و یک یعنی عالیه!
بر حسب سلامتی کرومزوم ها چند تا از اون ها به عنوان والدین نسل بعدی انتخاب میشن! مرحله ی بعدی مرحله ی Breed هست که طبق فرایند Crossover کرومزوم ها با هم ازدواج می کنن و بچه دار میشن!

وااای مگه یه مشت صفرو یکم می تونن با هم ازدواج کنن!

" یکم صبر کنی میبینی که می تونن! "

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

كد:

First pair:
00001|011
00100|010
After crossover:
00001010
00100011

در بالا فرآیند Crossover رو برای زوج اول می بینید! همونطور که مشخصه اول هر کزومزوم از بیت 5ام به دو قسمت تقسیم شدن و 5 بیت اول کرومزوم اول با 3 بیت دوم کرومزوم دوم ترکیب شده و برعکس. به این ترتیب دو فرزند جدید بوجود اومد.
همین کار برای بقیه ی کرومزوم ها هم انجام میشه، ممکنه یک کرومزوم دو یا چند بار در فرآیند Crossover بکار برده شه، احتمال شرکت کرومزوم هایی که سلامت بهتری دارند توی فرآیند Crossover بیشتره!
بعد از فرآیند Crossover یک مرحله داریم که احتمال وقوعش خیلی کم هست به نام جهش یا Mutation. توی این فرآیند یک بیت تصادفی از یه کرومزوم تصادفی رو عوض می کنند. مثلا اگر بیت چهارم یک کرومزوم انتخاب بشه در صورتی که صفر باشه اونو یک می کنند یا بلعکس.

كد:

First chromosome:
00001011
After mutation:
00011011

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

منبع: سیاوش محمودیان - بلاگ - مقدمه ای بر هوش مصنوعی

__________________

www.Syavash.com

فکر کنم جواب دادن به این سوال یه مقدار سخت باشه. چون در حال حاضر ما حتی تعریف دقیقی برای هوش نداریم!
واژه ی هوش مصنوعی (Artificial Intelligence) اولین بار توسط شخصی به نام John McCarthy استفاده شد با این تعریف: "علم و مهندسی ساخت ماشین های هوشمند".
اینم یه تعریف دیگه از هوش مصنوعی که تو خیلی از منابع بکار رفته:
" هوش مصنوعی عبارت است از مطالعه ی این که چگونه کامپیوترها را میی توان وادار به کارهایی کرد که در حال حاضر انسان‌ها آنها رابهتر انجام می‌دهند "
خوب من کلا زیاد از تعریف خوشم نمی یاد، در نتیجه این قسمت رو همینجا خاتمه میدم، با مثال فکر کنم بهتر بشه مفاهیم رو نشون داد! در آخر اگر دوست داشتین تعریفی که خودتون از هوش مصنوعی پیدا کردینو بگید!تاریخ هوش مصنوعی

بقیه در ادامه ی مطلب

ادامه مطلب

منطق فازی یا Fuzzy Logic در سال 1965 توسط دکتر لطفی زاده معرفی شد.
منطق فازی در واقع میگه که یه گزاره لزومی نداری یا درست باشه یا غلط (صفر باشه یا یک) ممکنه مثلا یه گزاره 0.7 درست باشه!
درکش یه مقدار در ابتدا سخته! بگذارید یه مثال بزنم، شما از دوستتون می پرسید بنظرت حسین بلنده یا نه؟ دوستتون جواب میده ایییی، بلند نیست اما کوتاه هم نمیشه بهش گفت! اما در منطق باینری (یا منطقی که اکثر ما باهاش تو کامپیوتر آشنا هستیم) هیچ وقت برای یه گزاره همچین جوابی نمیده.
توی منطق باینری ما میگیم اگه قد مساوی یا بلند تر از 175 بود بگو بلند اگه کوتاه تر بود بگو کوتاه! اما آدم اینطوری نیست منطقش مثل مثال قبلی که زدم.
حالا این سوال پیش میاد که ما در حال حاضر از همین منطق باینری جواب های خیلی خوبی میگیریم، فازی به چه دردی میخوره؟
برای جواب به این سوال یه مثال دیگه میزنم! مثلا یه شرکت می خواد یه کارخونه بزنه در فاصله ی ماکزیمم 200 کیلومتری تهران، که به تولید کننده ی یه مدل مواد اولیه نزدیک تر از 10 کیلومتر باشه و قیمت زمین هم اونجا هر چی کمتر باشه بهتر.اول یه بار با منطق باینری میریم پیش، اولین نمونه فاصلش با تهران 190 هست و با مواد اولیه هم 9 کیلومتر فاصله داره و قیمت زمین هم اونجا 2000 واحد هست، چندین تا نمونه دیگه هم برسی میشن که دو شرط اول رو ندارن، در آخر هم یه نمونه پیدا میشه که فاصلش تا تهران 201 کیلومتر هست و فاصلش با مواد اولیه 3 کیلومتره و قیمتش هم 1000 واحده! طبق منطق باینری این نمونه رد میشه چون فاصلش 201 هست و بیشتر از 200! اما حالا فرض کنید خود شما دارین تصمییم میگیرین، می یاین می بینید دو شرط آخر این مورد خیلی بهتر از اولین نمونس و تنها مشکل شرط اوله که 1 کیلومتر بیشتر از اون چیزیه که میخواین، با خودتون میگید خوب 1 کیلومتر در مقابل اون شرایط خوب که چیزی نیس و این مورد آخر رو انتخاب می کنید!
منطق فازی دقیقا همینو میگه! یعنی مثل منطق باینری که کاملا سخت گیرانه شرایط رو چک میکنه عمل نمی کنه بلکه مثل مغز آدم انعطاف پذیره.
این روزا تو خیلی چیزها از منطق فازی استفاده میشه، مثلا چند تاشون که شاید جالب باشن اینان:

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

ادامه ی مقاله را در ادامه ی مطلب بخوانید

ادامه مطلب

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

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