پسر لینوکسی
پسر لینوکسی
خواندن ۶ دقیقه·۲ سال پیش

تاریخچه کوتاهی از بهینه‌سازی


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

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

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

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

بهینه‌سازی در قبل از ۱۹۰۰ میلادی

مطالعه مسائل بهینه‌سازی دقیقا به اندازه خود علم قدیمی است. معروف است که ریاضیدانان یونان بوستان برخی مسائل بهینه‌سازی را حل کرده‌اند. برای مثال، در ۳۰۰ قبل میلاد، اقلیدس اثبات کرد که در میان مستطیل‌های با مجموع طول ضلع‌های یکسان، مربع بیشترین مساحت را دارد. در حدود ۱۰۰ قبل میلاد، هرون نشان داد که که فاصله بین دو نقطه در امتداد مسیر منعکس شده توسط یک آینه زمانی که نور حرکت می‌کند و از آینه منعکس می‌شود کوتاه‌ترین فاصله است، یعنی زاویه تابش برابر با زاویه بازتاب است. این یک مسئله بهینه‌سازی معروف به نام مسئله هرون است.

جانس کپلر، ستاره‌شناس مشهور آلمانی که شهرتش مدیون کشف سه قانون حرکت سیاره‌ای است، در ۱۶۱۳ یک راه حل بهینه برای یک مسئله بهینه‌سازی به نام مسئله ازدواج یا مسئله منشی ارائه داد. دلیل اینکه چرا او این مسئله را حل کرد به زمانی برمی‌گردد که دنبال زن دوم می‌گشت. وی روش حل این مسئله را در نامه شخصی که در ۲۳ اکتبر ‍‍۱۶۱۳ به بارون استراهلندروف نوشت توضیح داد. در نامه خود آورده بود که ۱۱ نفر برای ازواج با آن‌ها انتخاب کرد و بایستی از میان این‌ها مبتنی بر برقرار کردن توازن میان فضایل و معایب هر کدام یکی را انتخاب کند. این فضایل و معایب باید با در نظر گرفتن، مهریه، تردید و توصیه دوستان نیز همراه می‌بود. در آخر کپر فرد پنجم جهت ازدواج برگزید، با اینکه دوستش فرد چهارم را بدو پیشنهاد کرده بود. این نامه این را می‌رساند که کپلر سعی می‌کرد یک راه‌حل بهینه برای حل این مسئله بیابد. این مسئله در سال ۱۹۶۰ توسط مارتین گاردنر در ستون بازی‌های ریاضی مجله Scientific American آورده شد. بعدها این مسئله به منجر به ایجاد زمینه بهینه‌سازی احتمالی چون مسائله بهینه‌سازی stopping شد.

در سال ۱۶۲۱ فردی به نام راین اسنل قانون شکست را کشف کرد اما کار وی منشتر نشده باقی ماند. بعدها، کریستیان هویگنز نتایج اسنل را در کتاب Dioptrica در سال 1703 ذکر کرد. این قانون به صورت مستقل توسط رنه دکارت دوباره کشف شد و در رساله خود به نام Discours de la Methode در 1637 منتشر کرد. این قانون به طور مستقل توسط رنه دکارت دوباره کشف شد و در رساله‌اش Discours de la Methode در سال 1637 منتشر شد. حدود 20 سال بعد، زمانی که شاگردان دکارت با پیر دو فرما تماس گرفتند و مکاتبات او با دکارت را جمع‌آوری کردند، فرما دوباره در سال 1657 به بررسی استدلال دکارت در رابطه با شکست نور پرداخت و همان نتایجی که اسنل و دکارت به دست آورده بودند این بار فرما از یک اصل اساسی‌تر به دست ‌آورد – نور همیشه در کوتاه‌ترین زمان در هر رسانه ای حرکت می‌کند، و این اصلاکنون به عنوان اصل فرما نامیده می‌شود، که پایه و اساس اپتیک مدرن را بنا نهاد.

در ۱۶۸۷، سر اسحاق نیوتن در مقاله‌ای به نام Principia Mathematica مسئله شکل بدن با حداقل مقاومت را که قبلاً در سال 1685 به عنوان یک مسئله پیشگام در بهینه سازی مطرح کرده بود، حل کرد، که اکنون یک مسئله حساب تغییرات است. در این مسئله هدف اصلی یافتن شکل یک جسم چرخشی متقارن بود تا مقاومت در برابر حرکت در یک سیال به حداقل برسد. سپس نیوتن قانون مقاومت بدن را ارائه داد. و جالبیت قضیه آن است که گالیله در ۱۶۳۸ در مقاله Discursi مسئله مشابه به آنچه نیوتن ارائه داده بود ارائه کرد.

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

در ۲۹ ژانویه ۱۶۹۷، نیوتن این چالش را به دست گرفت و وقتی که ساعت ۴ بعد از ظهر به خانه رفت این مسئله را زمین ننهاد و دست از آن نکشید تا ساعت۴ بامداد همان روز راه‌حل را یافت. با اینکه نیوتن این مسئله را در کمتر از ۱۲ ساعت حل کرد، از آنجا که او سرپرست ضرابخانه سلطنتی بود، برخی می‌گفتند وی به عنوان یک نابغه باید چنین مسئله را در نیم ساعت حل می‌کرد. برخی ادعا می‌کردند که این مورد نشان دهنده آن است که کارهای اداری فراوان ذهن را فرسوده می‌کنیم. اکنون می‌دانیم که این مسئله بخشی از یک سیکلوید است.

در ۱۷۴۶ ، اصل کمترین کنش توسط مائوپرتیوس برای یکی کردن همه قوانین حرکت فیزیک و به کار بردن آن برای توضیح تمامی پدیده‌ها استفاده شد. در ترمینولوژی مدن، این یک اصل متغیر از کنش ثابت بر حسب معادله انتگرال یک تابع در چارچوب حساب تغییرات است که در مکانیک کلاسیک لاگرانژی و همیلتونی نقش محوری دارد. همچنین یک اصل مهم در ریاضیات و فیزیک است.

در ۱۷۸۱، گاسپارد مونگ، یک مهندس عمران فرانسوی، مسئله حمل و نقل برای انتقال بهینه و تخصیص بهینه منابع برسی کرد. در ۱۹۴۲، لئونید کانتوروویچ نشان داد که این مسئله بهینه سازی ترکیبی در واقع یک مسئله برنامه ریزی خطی است

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