الگوریتم‌های تطبیقی

الگوریتم‌های تطبیقی دسته‌ای از الگوریتم‌ها می‌باشند که رفتار خود را براساس اطلاعات موجود طی اجرای الگوریتم تغییر می‌دهند. این اطلاعات می‌توانند داده‌هایی که اخیراً وارد الگوریتم شده‌اند یا اطلاعات موجود در منابع اطلاعاتی باشند.

پرکاربردترین الگوریتم تطبیقی فیلتر کمترین مربعات ویدرو-هاف می‌باشد که یک دسته از الگوریتم‌های تصادفی نزولی‌شیب را ارائه می‌دهد که در فیلترینگ تصادفی و یادگیری ماشین کاربرد دارند. در الگوریتم‌های تطبیقی فیلتر کمترین مربعات برای تقلید یک فیلتر دلخواه با پیدا کردن ضرایب فیلتری که مربوط به تولید سیگنال خطای کمترین مربعات است استفاده می‌گردد.

نحوه عملکرد الگوریتم تطبیقی

کاربرد

سیستم رادار

یکی از کاربردهای الگوریتم‌های تطبیقی در سیستم‌های راداری، تعیین نرخ ثابت خطا(CFAR) می‌باشد.

از کارهای مهم در زمینه رادار تشخیص هدف می‌باشد که توسط CFAR قابل‌انجام می‌باشد. آستانه تشخیص هدف که با T نمایش داده می‌شود توسط فرمول T=αPn محاسبه می‌گردد.Pn برابر با قدرت نویز می‌باشد که توسط سلول‌های همسایه اندازه‌گیری می‌گردد و α برابر ثابت آستانه تشخیص می‌باشد.

از روی فرمول مشخص است که مقدار آستانه تشخیص مطابق با داده می‌باشد؛ بنابراین CFAR آلگوریتمی تطبیقی می‌باشد.

یادگیری ماشین

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

پردازش سیگنال

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

تقسیم‌بندی پایدار

تقسیم‌بندی پایدار(stable partition) اگر بدون استفاده از حافظه اضافی انجام گیرد در (O(n lg n قابل انجام است. اما اگر به اندازه (O(n حافظه اضافه تخصیص دهیم، این عمل در (O(n قابل انجام می‌باشد که در کتابخانه استاندارد ++C پیاده‌سازی شده‌است.

stable_partition یک الگوریتم تطبیقی در ++C می‌باشد و به مقداری که امکان دارد حافظه اضافی برای الگوریتم تخصیص می‌دهد و الگوریتم را با استفاده از مقدار حافظه کنار گذاشته‌شده پیش می‌برد.

مرتب‌سازی تطبیقی

مرتب‌سازی درجی

مثالی کلاسیک از الگوریتم مرتب‌سازی تطبیقی مرتب‌سازی درجی(Straight Insertion Sort) می‌باشد. در این الگوریتم مرتب‌سازی ورودی را از چپ به راست پیمایش می‌نماییم، مکرراً موقعیت عنصر فعلی را پیدا می‌کنیم و آن را وارد آرایه‌ای که براساس عناصر قبلی مرتب‌شده‌است می‌نماییم. نوع دیگر این الگوریتم مرتب‌سازی درجی دودویی(binary insertion sort) می‌باشد که برای درج عنصر فعلی در آرایه مرتب شده از جستجوی دودویی استفاده می‌نماید. در زیر تصویری از نحوه عملکرد مرتب‌سازی درجی به همراه شبه‌کد آورده شده‌است.

عملکرد الگوریتم مرتب‌سازی درجی

procedure Straight Insertion Sort (X):
for j := 1 downto length(X) - 1 do
        t := X[j]
        i := j
        while i> 0 and X[i - 1]> t do
            X[i] := X[i - 1]
            i := i - 1
        end
        X[i] := t
    end

مرتب‌سازی هرمی تطبیقی

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

مرتب‌سازی تیم

مرتب‌سازی تیم(timsort) یک الگوریتم مرتب‌سازی پایدار می‌باشد که از ترکیب مرتب‌سازی ادغامی و مرتب‌سازی درجی ایجاد شده‌است. این الگوریتم برای بسیاری از داده‌های مورد استفاده در دنیای واقعی به‌خوبی عمل می‌نماید. زمان اجرای این الگوریتم در بدترین حالت برابر با (O(n lg n می‌باشد اما در بهترین‌حالت (O(n است که نشان‌دهنده تطبیقی بودن این الگوریتم می‌باشد.

جستارهای وابسته

• الگوریتم
• مرتب‌سازی درجی
• آدابوست
• پردازش سیگنال
• یادگیری‌ماشین