بایگانی برچسب برای: ;kjvg jvnn

زنجیره مارکوف (Markov Approach modeling) قسمت 4

زنجیره ارگودیک و زنجیره باقاعده

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

متوسط زمان اصابت

در یک زنجیره ارگودیک زمان اولین بار رسیدن یا اصابت به حالت j در حالی که زنجیر مارکوف در حالت i بوده‌است، زمان اصابت از i به j نامیده می‌شود. زمان اصابت با متغیر تصادفی $T_{ij}$ به صورت زیر توصیف می‌شود:

$T_{ij}=\inf\{n\geq 1:X_{n}=j|X_{0}=i\}.$

متوسط زمان اصابت از i به j، یعنی $H_{ij}=E[T_{ij}]$ ، از رابطهٔ بازگشتی زیر بدست می‌آید:

H_{ij}=\sum _{r\in S}p_{ir}H_{rj}

تجزیه و تحلیل توزیع ثابت و محدود کردن توزیع‌ها

برای یک زنجیر یکنواخت در زمان، بردار ${\boldsymbol {\pi }}$ یک «توزیع ثابت» (یا ایستا) نامیده می‌شود اگر $\pi _{j}$ ‌ها نامنفی و جمع آن‌ها برابر ۱ شود و نیز در رابطه زیر صدق کنند:

$\pi _{j}=\sum _{i\in S}\pi _{i}p_{ij}.$

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

$\pi _{j}={\frac {1}{M_{j}}}.\,$

اگر زنجیره باقاعده (غیر تقلیل پذیر و غیر متناوب) باشد آن گاه برای هر i و j داریم:

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {1}{M_{j}}}.$

لازم است ذکر شود که هیچ شرطی روی نقطه شروع توزیع وجود ندارد یعنی زنجیره صرف نظر از نقطه شروع به توزیع ثابت میل می‌کند. این π «توزیع تعادل» زنجیره نامیده می‌شود. اگر زنجیره بیش از یک کلاس مرتبط بسته داشته باشد توزیع ثابت آن یکتا نخواهد بود. زنجیره غیر یکنواخت در زمان نیز می‌تواند توزیع تعادل داشته باشد.

در هر صورت اگر حالت j ام غیر متناوب باشد آن گاه:

$\lim _{n\rightarrow \infty }p_{jj}^{(n)}={\frac {1}{M_{j}}}$

و برای هر حالت i دیگر اگر f_ij احتمال این باشد که زنجیره در حالت j قرار گیرد در صورتی که شروع زنجیره از حالت i باشد خواهیم داشت:

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {f_{ij}}{M_{j}}}.$

اگر حالت i متناوب باشد با دوره تناوب k > 1 آنگاه حد

$\lim _{n\rightarrow \infty }p_{ii}^{(n)}$

وجود ندارد و نیز حد

$\lim _{n\rightarrow \infty }p_{ii}^{(kn+r)}$

برای هر r صحیح وجود ندارد.

زنجیره وارون پذیر

یک زنجیره مارکوف وارون پذیر نامیده می‌شود اگر یک توزیع احتمال $\pi$ بر روی حالتها وجود داشته باشد به‌طوری‌که برای تمام زمان‌های n و حالتهای i و j رابطهٔ زیر برقرار باشد:

$\pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)$

برای زنجیره‌های یکنواخت در زمان رابطهٔ بالا به صورت سادهٔ زیر نوشته می‌شود:

\pi _{i}p_{ij}=\pi _{j}p_{ji}\,.

توزیع احتمال $\pi$ در رابطهٔ بالا همان توزیع ثابت در زنجیره‌های ارگودیک می‌باشد.

کاربردها

فیزیک

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

علم اطلاعات

زنجیره مارکوف در نظریه اطلاعات کاربرد دارد. مقاله معروف کلود شانون در سال ۱۹۴۸ با «نظریه ریاضی ارتباطات» که پایه‌گذار نظریه اطلاعات شد با معرفی آنتروپی از طریق مدل‌سازی مارکوف از زبان انگلیسی آغاز می‌شود. چنین مدل‌های ایده‌آلی بسیاری از قواعد آماری سیستم را به دست می‌دهند. حتی بدون داشتن ساختار کامل سیستم این گونه مدل‌سازی‌ها فشرده سازی مؤثر داده‌ها را ممکن می‌سازند.

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

نظریه صف

زنجیره‌های مارکوف اساس رفتار تحلیلی صف ها(نظریه صف) می‌باشد و این امر وجود آن‌ها را برای بهینه‌سازی عملکرد شبکه‌های مخابراتی حیاتی می‌سازد. جایی که پیام‌ها برای منابع محدود (مانند پهنای باند) رقابت می‌کنند. مدل‌های صف بندی بسیاری از زنجیره مارکوف زمان پیوسته استفاده می‌کنند. برای مثال، یک صف M / M / 1 یک CTMC بر روی عدد صحیح غیر منفی است که در آن انتقال از i به i + 1 بر اساس یک فرایند پوآسون با نرخ λ رخ می‌دهد و ورود کار را توصیف می‌کند، در حالی که انتقال از i به i – 1 (برای i> 1) در نرخ μ اتفاق می‌افتد (بار خدمات شغلی از توزیع نمایی پیروی می‌کنند) و خدمات کامل یا همان خروج از صف را نشان می‌دهد.

نمایش سادهٔ شبکه‌ای از چند صفحه که با رتبه صفحه ارزیابی شده‌اند.

کاربرد اینترنتی

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

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

منبع

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

زنجیره مارکوف بر اصل بدون یادآوری یا بی حافظه بنا شده است به این معنی که حالت بعدی سیستم، به حالت های قبلی آن بستگی ندارد. با این اصل، محاسبه احتمال عملیات مجاز بعدی بسیار ساده تر خواهد بود. البته حالت پیشرفته تری از زنجیره مارکوف با نام Latent MC در کاربردهای دنیای واقعی که وابستگی به عملیات قبلی هم جزء الزامات پیش بینی ها خواهد بود، استفاده میشود که در اینجا به آن نمی پردازیم.

یک مثال عملی

فرض کنید دو شرکت Coke و Pepsi تنها شرکتهای تولید کننده یک ماده غذایی در کشور X هستند، شرکت Y قصد انتخاب یک شریک تجاری از بین این دو رقیب را دارد. آنها از یک شرکت تحلیلگر بازار خواسته اند که شرایط بازار را برای هر دو برند بررسی کند .شرکتی که بعد از یکماه بیشترین سهم بازار را داشته باشد، برنده این شراکت خواهد بود .

شرکت تحلیل گر نتایج زیر را بعد از بررسی بازار ارائه داده است :

P(P->P) = 0.7 – احتمال ماندن مشتریان برند Pepsi بعد از یکماه با برند Pepsi

P(P->C) = 0.3 – احتمال تغییر شرکت مشتریان Pepsi بعد از یکماه به برند Coke

P(C->C) = 0.9 – حتمال ماندن مشتریان برند Coke بعد از یکماه با برند Coke

P(C->P) = 0.1 – حتمال تغییر شرکت مشتریان Coke بعد از یکماه به برند Pepsi

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

زنجیره مارکوف (Markov Approach modeling) قسمت 1
زنجیره مارکوف (Markov Approach modeling) قسمت 2
زنجیره مارکوف (Markov Approach modeling) قسمت 3
زنجیره مارکوف (Markov Approach modeling) قسمت 4
زنجیره مارکوف (Markov Approach modeling) قسمت 5

نوامبر 1, 2019/0 دیدگاه /توسط hgadmin

زنجیره مارکوف (Markov Approach modeling) قسمت 3

آموزش عمومی پردازش تصویر و بینایی ماشین

تکامل گذرا

احتمال تغییر حالت از حالت iام به حالت jام در n حرکت برابر است با

p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,

این احتمال در یک حرکت برابر است با

p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,

برای یک زنجیره مارکوف یکنواخت در زمان

$p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)\,$

$p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i)\,$

توجه کنید که برای یک زنجیره مارکوف یکنواخت در زمان، احتمال تغییر حالت از حالت iام به حالت jام در n حرکت معادل است با درایهٔ (i,j) ام ماتریس احتمال انتقال وقتی این ماتریس n بار در خودش ضرب شده‌است:

$p_{ij}^{(n)}=[P^{n}]_{ij}$

در حرکت‌های n تایی احتمالات بدست آمده برابری چپمن-کولموگروف را ارضا می‌کنند. پس برای هر k که ۰ <n> k داریم

p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}

در این رابطه S فضای حالت زنجیره مارکوف است. توزیع حاشیه ای (Pr(X_n = x مربوط به حرکت nام است. توزیع اولیه برابر است با (Pr(X_۰ = x. تعمیم یافته این توزیع برای حرکت‌های بعدی به شکل

$\Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r).$

نمایش داده می‌شود که در آن n زیروند است و نه توان.

رده‌بندی حالت‌های یک زنجیر مارکوف

تقلیل‌پذیری

حالت jام را قابل دسترسی از حالت iام می‌نامند (i → j) اگر در سیستمی که از حالت iام شروع شود با احتمال غیر ۰ در نهایت به حالت jام برسد. در واقع اگر عدد صحیح n ≥ ۰ وجود داشته باشد که

\Pr(X_{n}=j|X_{0}=i)=p_{ij}^{(n)}>0.\,

تساوی n با ۰ به معنای در دسترس بودن همه حالات از حالت iام است. حالت iام را مرتبط با حالت jام می‌نامند (i ↔ j) اگر هر دو رابطه i → j و j → i برقرار باشند.

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

یک کلاس هم‌ارزی را بسته می‌نامند اگر احتمال خروج از این کلاس ۰ باشد. به عبارت دیگر اگر حالت i در C باشد و حالت j در C نباشد، j قابل دسترسی از i نیست. مجموعه‌ای از کلاس‌های مرتبط یک گراف جهت‌دار بدون دور را تشکیل می‌دهند که یال‌های آن همان یال‌های فضای حالت اصلی هستند. یک کلاس مرتبط بسته‌است اگر و تنها اگر هیچ یال خروجی میان کلاس‌های مختلف وجود نداشته باشد.

حالت i را ضروری می‌نامند اگر به ازای همه jهایی که i → j، رابطه j → i نیز برقرار باشد. در غیر این صورت حالت i را غیرضروری می‌نامند.

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

تناوب

حالت i دارای دوره تناوب k است اگر هر مسیر بازگشت به حالت i به طول مضارب k باشد. به زبان دیگر دوره تناوب یک حالت برابر است با

k=\operatorname {gcd} \{n:\Pr(X_{n}=i|X_{0}=i)>0\}

که در آن gcd بزرگترین مقسوم علیه مشترک است. اگر یک حالت دوره تناوب k داشته باشد ممکن است نتوان به این حالت با k حرکت رسید. به‌طور مثال اگر بتوان به حالت i در {۶, ۸, ۱۰, ۱۲, …} حرکت بازگشت، در این صورت دوره تناوب برابر ۲ خواهد بود حتی اگر ۲ در مقادیر ذکر شده نباشد. اگر k = ۱ باشد، در این صورت به حالت مد نظر غیر متناوب می‌گویند و بازگشت به حالت i در حرکت‌های غیر منظم انجام خواهد گرفت. در غیر این صورت (k > 1)، حالت iدارای دوره تناوب k و متناوب می‌باشد.

بازگشت‌پذیری

فرض کنید f_i احتمال این پیشامد باشد که زنجیر با شروع از وضعیت i بعد از تعداد متناهی تغییر وضعیت به i برگردد. به وضوح $f_{i}=\sum _{n=1}^{\infty }f_{ii}^{n}\,$ . اگر $f_{i}=1$ در این صورت حالت i را بازگشتی یا پایامی‌گوییم. به این ترتیب هر بار که زنجیر در حالت i قرار می‌گیرد فرایند به‌طور احتمالی حرکت خود را از سر شروع می‌کند، لذا اولین بازگشت به i مستلزم بازگشت دوم به i، و الی آخر است؛ بنابراین اگر i حالت بازگشتی باشد، فرایند با احتمال ۱ بینهایت بار به i برمی‌گردد و احتمال اولین بازگشت به این حالت در زمان متناهی برابر ۱ است. اگر امید ریاضی تعداد تغییر وضعیت‌ها تا بازگشت مجدد به i متناهی باشد به i بازگشتی مثبت و در غیر این صورت بازگشتی پوچ می‌گوییم.

حالت i را گذرا می‌نامند هرگاه $f_{i}<1$ ، به این معنی که اگر سیستم از حالت i شروع به کار کند، احتمال این که دیگر به این حالت بازنگردد غیر صفر است. برای حالت گذرای i احتمال این که فرایند با شروع از i دقیقاً بعد از n بار به آن بازگردد برابر است با $(f_{i})^{n}(1-f_{i})$ . پس تعداد بازگشت‌ها به i متغیر تصادفی با پارامتر $1-f_{i}$ می‌باشد، درنتیجه تعداد بازگشت‌ها بینهایت نمی‌شود.

با در نظر گرفتن متغیر تصادفی T_i، زمان اولین بازگشت به حالت i، داریم:

T_{i}=\inf\{n\geq 1:X_{n}=i|X_{0}=i\}.

عدد $f_{ii}^{(n)}=\Pr(T_{i}=n)$ احتمال بازگشت سیستم به حالت i برای اولین بار در حرکت nام است. در نتیجه حالت i گذرا است اگر

$\Pr(T_{i}<{\infty })=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1$

متوسط زمان بازگشت

اگر زمان اولین بازگشت به حالت i با احتمال ۱ متناهی باشد، نمی‌توان نتیجه گرفت که امید ریاضی این زمان متناهی است. امید ریاضی زمان بازگشت به حالت i همان متوسط زمان بازگشت است که از رابطه

M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.\,

محاسبه می‌شود.

متوسط تعداد بازگشت‌ها

می‌توان نشان داد که حالت i پایا است اگر و تنها اگر متوسط تعداد بازگشت‌ها به این حالت نامتناهی باشد. یعنی

\sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .

چند قضیه مهم

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

حالت‌های مانا

حالت i را جذب‌کننده یا مانا می‌نامند اگر با ورود به این حالت خروج از آن غیرممکن باشد. در نتیجه حالت i مانا است اگر و تنها اگر

p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.

اگر هر حالت در یک سیستم به حالت مانایی برسد زنجیره مارکوف را زنجیره مارکوف مانا می‌نامند.

نوامبر 1, 2019/0 دیدگاه /توسط hgadmin

زنجیره مارکوف (Markov Approach modeling) قسمت 2

آموزش عمومی پردازش تصویر و بینایی ماشین

تعریف رسمی

زنجیره مارکوف زمان گسسته

یک زنجیره مارکوف دنباله‌ای از متغیرهای تصادفی X_۱،X_۲،X_۳،… است که دارای خاصیت مارکوف هستند یعنی:

$\Pr(X_{n+1}=x|X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x|X_{n}=x_{n}).\,$

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

زنجیره مارکوف اغلب توسط دنباله‌ای از گراف‌های جهت‌دار نشان داده می‌شود، که در آن یال‌های گراف n توسط احتمال از رفتن از یک حالت در زمان n به حالت‌های دیگر در زمان n + 1 برچسب گذاری شده‌است. همان اطلاعات در ماتریس انتقال از زمان n به زمان n + 1 درج می‌شود که در آن عنصر سطر i و ستون j، احتمال تغییر وضعیت از حالت i-1 به حالت j-1 است. مجموع عناصر هر سطر برابر یک است اما الزاماً مجموع عناصر هر ستون یک نمی‌شود. در نظریه ماتریس‌ها اگر تمام عناصر ماتریسی نامنفی و مجموع عناصر هر سطر یک باشد، در این صورت آن ماتریس را ماتریس مارکوف می‌گویند. علت آن است که برای چنین ماتریس‌هایی می‌توانیم یک فضای نمونه بسازیم به طوری که عناصر ماتریس، احتمال‌های تغیر وضعیت تمام پیشامدهای فضای نمونه باشند و سپس یک زنجیر مارکوف برای فضای نمونه تعریف کنیم. با این حال، زنجیره‌های مارکوف اغلب به صورت یکنواخت در زمان فرض می‌شوند در این صورت گراف و ماتریس مستقل از n هستند و به این ترتیب به شکل یک توالی ارائه نمی‌شوند.

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

زنجیره‌های مارکوف یکنواخت در زمان

زنجیره‌های مارکوف یکنواخت در زمان، یا ایستا، زنجیره‌هایی هستند که در آن‌ها:

$\Pr(X_{n+1}=x|X_{n}=y)=\Pr(X_{n}=x|X_{n-1}=y)\,$

که رابطه بالا برای هر n صحیح است. در واقع احتمال انتقال مستقل از n است. چنین زنجیره‌هایی را می‌توان تنها با یک ماتریس احتمال انتقال $P$ توصیف کرد. ماتریس احتمال انتقال $P$ مستقل از زمان n است و درایهٔ (i,j) ام آن، یعنی $p_{ij}$ ، بیانگر احتمال انتقال از حالت i به حالت j می‌باشد.

زنجیره مارکوف مرتبه m

زنجیره مارکوف مرتبه m (که در آن m متناهی است) فرایندی است که در آن:

${\begin{aligned}{}&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}$

به عبارت دیگر حالت بعدی به m حالت قبلی وابسته‌است. می‌توان یک {Y_n} از {X_n} ساخت به طوری که در فرم کلاسیک خاصیت مارکوف صدق کند؛ که در این صورت Y یک چندتایی مرتب از Xها است یعنی: $Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)$

زنجیره مارکوف افزاینده

یک زنجیره مارکوف افزاینده مرتبه m با رابطه زیر توصیف می‌شود:

$\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m})=\sum _{r=1}^{m}f(x_{n},x_{n-r},r).$

زنجیره مارکوف زمان پیوسته

لامپی را در نظر بگیرید که یا روشن است یا خاموش. اگر لامپ در زمان t روشن باشد X(t) = 1 و اگر خاموش باشد X(t) = 0. در این صورت متغیر تصادفی X زمان گسسته نیست زیرا پس از ورود به حالتی برای یک مدت زمانی که خود نیز متغیری تصادفی است، در آن جا می‌ماند و سپس به حالت دیگری منتقل می‌شود. این قبیل فرایندها را زنجیره مارکوف زمان پیوسته می‌نامیم.

یک زنجیره پیوسته مارکف توسط یک فضای حالت متناهی یا شمارا، یک ماتریس نرخ انتقال Q با ابعادی برابر با فضای حالت است. برای i ≠ j، هر عنصر q_ij غیر منفی است و نرخ انتقال فرایند را از حالت i به حالت j توصیف می‌کند.

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

تعریف حدی

اگر متغیر تصادفی وضعیت زنجیره درلحظهٔ t با X_t نشان دهیم و فرض کنیم زنجیره در زمان t در حالت i قرار دارد. با توجه به این که X_t = i و X_t+h به مقادیر گذشته وابسته نیستند، هنگامی که h → ۰ برای هر j و t داریم:

\Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h)

که در این معادله $\delta _{ij}$ دلتای کرونکر است و همچنین از نماد o کوچک استفاده شده‌است. q_ij می‌تواند معیاری از سرعت تغییر حالت از i به j باشد.

تعریف زنجیره پرش یا زمان نگهداری

اگر متغیر تصادفی Y_n نشان‌دهندهٔ nامین پرش (تغییر حالت) در زنجیره باشد و متغیرهای $S_{1},S_{2},S_{3},...$ زمان ایستایی در هر حالت را نشان دهند، هر کدام از S_iها از توزیعی نمایی با پارامتر $q_{Y_{i}Y_{i}}$ پیروی می‌کنند.

تعریف احتمال انتقال

برای هر مقدار $n=0,1,2,...$ و زمان‌های $t_{0},t_{1},t_{2},...$ با حالت‌های $i_{0},i_{1},i_{2},...$ داریم:

\Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{0}}=i_{0},X_{t_{1}}=i_{1},\ldots ,X_{t_{n}}=i_{n})=p_{i_{n}i_{n+1}}(t_{n+1}-t_{n})

که در آن p_ij در دو مجموعه معادلات دیفرانسیلی به نام‌های معادلات پیشرو کولموگروف و معادلات پسرو کولموگروف en:Kolmogorov equations صدق می‌کنند.

اکتبر 31, 2019/0 دیدگاه /توسط hgadmin

زنجیره مارکوف (Markov Approach modeling) قسمت 1

آموزش عمومی پردازش تصویر و بینایی ماشین

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

نمونه‌ای از زنجیره مارکوف با سه حالت

معرفی

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

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

یکی از معروف‌ترین زنجیره‌های مارکوف که موسوم به «پیاده‌روی می خواره» است یک پیاده‌روی تصادفی است که در آن در هر قدم موقعیت با احتمال برابر به اندازه ۱+ یا ۱- تغییر می‌کند. در هر مکان دو انتقال ممکن وجود دارد یکی به عدد صحیح بعدی(۱+) و یکی به عدد صحیح قبلی(۱-). احتمال هر انتقال فقط به حالت کنونی بستگی دارد. برای مثال احتمال انتقال از ۵ به ۶ برابر با احتمال انتقال از ۵ به ۴ است و هر دوی این احتمالات برابر با ۰٫۵ هستند. این احتمالات مستقل از حالت قبلی (که یا ۴ بوده یا ۶) هستند.

مثالی دیگر عادات غذایی موجودی است که فقط انگور، پنیر و کاهو می‌خورد و عادات غذایی او از قوانین زیر پیروی می‌کند:

او فقط یک بار در روز غذا می‌خورد.
اگر امروز پنیر بخورد فردا انگور یا کاهو را با احتمال برابر خواهد خورد.
اگر امروز انگور بخورد فردا با احتمال ۰٫۱ انگور، با احتمال ۰٫۴ پنیر و با احتمال ۰٫۵ کاهو خواهد خورد.
اگر امروز کاهو بخورد فردا با احتمال ۰٫۴ انگور و با احتمال ۰٫۶ پنیر خواهد خورد.

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

مثال‌هایی از زنجیره مارکوف

ورشکستگی قمارباز

ورشکستگی قمارباز مسئله‌ای معروف از زنجیره مارکوف است. در این مسئله دو فرد تاس می‌اندازند و هر بار که سکه شیر آمد شخص A یک دلار از B می‌برد و هر بار سکه خط بیاید، شخص B یک دلار از A می‌برد. در ابتدای بازی A مقدار a دلار و B مقدار b دلار دارد. فرض کنید X_i دارایی A پس از i مرحله بازی باشد. یکی از خواص دنباله {X_i} این است که اگر در مرحلهٔ nام مقدار X_i را بدانیم در این صورت سرمایه A از آن مرحله به بعد تنها به X_n و نه به X₀, X₁, …, X_n-1 وابسته است. یعنی اگر سرمایهٔ A در زمان حال معلوم باشد، سرمایهٔ آیندهٔ او مستقل از پولی است که در هر مرحله از بازی در گذشته برنده شده یا باخته‌است.

فرایند زاد مرگ

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

بازی‌های تخته‌ای با تاس

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

گام‌های تصادفی متمایل به مرکز

یک حرکت تصادفی روی تعدادی خط را در نظر بگیرید، موقعیت کنونی (که x نامیده می‌نامیم) با احتمالات زیر می‌تواند به +۱ (به راست) یا -۱(به چپ) تغییر کند:

(c یک عدد ثابت بزرگتر از ۰ است)

به عنوان مثال اگر عدد ثابت c برابر ۱ باشد، احتمال حرکت به چپ از موقعیت x=-۲,-۱٬۰٬۱٬۲ به ترتیب برابرست با:.

یک گام تصادفی یک اثر مرکزی دارد به‌طوری‌که با افزایش تضعیف c می‌شود. از آنجایی که احتمالات تنها به وضعیت کنونی بستگی دارد (مقدار x) و وابسته به هیچ‌یک از موقعیت‌های قبلی نیست، این گام تصادفی متمایل به مرکز در تعریف زنجیرهٔ مارکوف صدق می‌کند.

یک مدل آب و هوایی بسیار ساده

نمونه‌ای ساده از یک مدل آب‌وهوایی

احتمال وضعیت آب و هوایی که آب و هوا در طول روز را نشان می‌دهد و هم به صورت بارانی و هم آفتابی مدل می‌شود، توسط یک ماتریس انتقال ارائه داده می‌شود. ماتریس P یک مدل آب و هوایی را نشان می‌دهد به‌طوری‌که روز بعد یک روز آفتابی، با احتمال %۹۰ آفتابی است و روز بعد یک روز بارانی، با احتمال %۵۰ آفتابی است. ستونها و سطرها با آفتابی و بارانی برچسب‌گذاری می‌شوند.

(P)_{i j} احتمال این است که هوای امروز از نوع i باشد و فردا از نوع j باشد.

در نظر داشته باشید که حاصل جمع احتمالات سطر P برابر ۱ است.

حالت ثابت آب و هوا

در این مثال، پیش‌بینی هوا در روزهای دور از هم غلط از آب در می‌آید و متمایل به بردار حالت پایدار است. این بردار احتمال هوای آفتابی و بارانی را در همهٔ روزها نشان می‌دهد و مستقل از آب وهوای اولیه است.

بردار حالت ثابت به این صورت تعریف می‌شود: $\mathbf {q} =\lim _{n\to \infty }\mathbf {x} ^{(n)}$

ولی تنها زمانی به یک مقدار منظم همگراست که p یک ماتریس انتقال منظم باشد (بعبارت دیگر حداکثر یک Pⁿ با ورودیهای غیر صفر وجود دارد)

از آنجایی که q مستقل از شرایط اولیه است، زمانی که بوسیلهٔ P ترجمه می‌شود، بایستی بدون تغییر بماند؛ که این باعث می‌شود که q تبدیل به بردار ویژه شود، به این معنی که از P مشتق شود. برای مثال آب و هوا:

${\begin{matrix}P&=&{\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}\\\mathbf {q} P&=&\mathbf {q} &{\mbox{(}}\mathbf {q} {\mbox{ is unchanged by }}P{\mbox{.)}}\\&=&\mathbf {q} I\\\mathbf {q} (P-I)&=&\mathbf {0} \\&=&\mathbf {q} \left({\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}-{\begin{bmatrix}1&0\\0&1\end{bmatrix}}\right)\\&=&\mathbf {q} {\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}\end{matrix}}$ ${\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}{\begin{bmatrix}-0.1&0.1\\0.5&-0.5\end{bmatrix}}={\begin{bmatrix}0&0\end{bmatrix}}$

پس $-0.1q_{1}+0.5q_{2}=0$ و از آنجایی که این دو بردار احتمال هستند، داریم $q_{1}+q_{2}=1$

حل این دو معادله یک توزیع حالت یکنواخت را می‌دهد:

${\begin{bmatrix}q_{1}&q_{2}\end{bmatrix}}={\begin{bmatrix}0.833&0.167\end{bmatrix}}$

در نتیجه %۸۳ روزها آفتابی است.

اکتبر 31, 2019/0 دیدگاه /توسط daliri

منطق فازی در هوش مصنوعی

هوش محاسباتی

مقدمه

منطق فازی شاید بیشترین امید به پیشرفت و شتاب در جامعه هوش مصنوعی در تاریخچه اخیر آن باشد. اما چرا بعضی واژه های نامعلوم به درستی پشت واژه « فازی» قرار می گیرند؟ چرا « فازی » موجب پیشرفت هوش مصنوعی می شود؟
پاسخ این سوالات در مقاله زیر داده شده است.

تاریخچه منطق فازی

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

منطق فازی چیست؟

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

واژگانی از قبیل { کم ، زیاد، خیلی کم ، خیلی زیاد، قدری و … } این واژه ها واژه های زبان شناختی نام دارند، یعنی با مقادیر ریاضی نمی توان مقدار مشخصی را به آنها ربط داد.
اینجاست که منطق فازی وارد عمل می شود و با استفاده از مجموعه های فازی،برای متغیر میزان بارش باران، مجموعه ای را به شکل زیر صورت می دهد:
میزان بارش باران= { کم ، زیاد، خیلی کم ، خیلی زیاد، قدری و … }

باید پذیرفت قواعدی نظیر این زیبا هستند، زیرا این ها قواعد بشری هستند. آنها نمونه خوبی هستند برای اینکه ما چطورفکر می کنیم و چطور نتیجه می گیریم. بیایید به سراغ نمونه دیگری برویم:
ازشما سوال می شود” آیا شغلتان را دوست دارید؟” پاسخ شما لزوماً بله یا خیر نمی باشد؛ بنابراین مجموعه جواب به صورت زیر خواهد بود:
جواب= { تا حدی، نه خیلی، تقریباً، اصلاً ، کم و بیش، خیلی و… }
به هر یک از این مقادیر،مقداری به عنوان ” درجه عضویت” نسبت داده می شود، بدین معنا که مقدار مربوطه تا چه حد در این مجموعه عضو می باشد.

مجموعه های فازی و زبان طبیعی

لازم به ذکر است، در مجموعه های قطعی، یک شیء قطعاً ، یا عضو مجموعه، است یا نیست:

اگر xعضو مجموعه A باشد
اگر X عضو مجموعه A نباشد

اما در مجموعه های فازی، یک شیء می تواند تا حدودی به یک مجموعه متعلق باشد:

که در این حالت تابع عضویت، یک عدد حقیقی است:

بدین معنا که شیء مورد نظر به طور نسبی در یک مجموعه وجود دارد. همچنین مقدار جزئی تابع عضویت، درجه عضویت نامیده می شود.
از سوی دیگر در نظر داشته باشید: مفاهیم ومجموعه های فازی ،عموماً در زبان طبیعی بکار می روند نظیر:
” جان قد بلند است.”
” هوا گرم است.”

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

پایین	قدری	تقریباً
متوسط	کم	بین
بالا	زیاد	به مقدار زیاد
خیلی	بیشتر
اصلاً	بیشترین
کم و بیش	در حدود

دراین تئوری، عضویت اعضای مجموعه از طریق تابع U ( X) مشخص می شود که X نمایانگر یک عضو مشخص و U تابعی فازی است که درجه عضویت X در مجموعه مربوطه را تعیین می کند و مقدار آن بین صفر و یک است:

همچنین به عنوان یک مجموعه متناهی از عناصر، برای عبارت بلند قد می توان زیر مجموعه فازی ذیل را تعریف کرد:
{ ( 8،1 )، ( 1، 705 )، ( 1، 7 )، (875،65 )، ( 05، 6 )،( 0125، 55 )،(0 ، 5 )}= بلند قد
در این مجموعه فازی، علامت “، ” درجه عضویت را از اعداد مربوطه به قد افراد جدا می سازد.

متغیرهای زبانی

” متغیرهای زبانی، متغیرهایی هستند که مقادیرشان اعداد نیستند،بلکه لغات یا جملات یک زبان طبیعی یا ساختگی هستند.”
به طورکلی، متغیرها به 2 دسته تقسیم می شوند:
زبانی: مانند کلمات و عبارات مربوطه به یک زبان طبیعی می باشد.
عددی: که متغیرها دارای مقادیرعددی هستند.

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

درعین حال متغیرهای زبانی می توانند از الحاق تشکیل شوند که هر کدام از uiها، عباتی تجزیه ناپذیر است. مانند ” تا حدی سرد “، که در مجموع به 4 دسته زیر تقسیم می شود:
عبارات اصلی: که به عنوان برچسب هایی برای مجموعه های فازی در نظر گرفته می شوند و مانند ” سرد” در عبارات بالا، یا عباراتی از قبیل : کوتاه، بلند و … که هر کدام تابع عضویت مخصوص خود را دارند.

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

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

اما چگونه منطق فازی به کار گرفته می شود؟

منطق فازی معمولاً از قوانین ” اگر و آنگاه” ( IF/THEN) استفاده می کند، اما این بررسی ،به صورت بررسی مقادیر خشک منطق کلاسیک نمی باشد، بلکه این بررسی توسط متغیرهای معنایی صورت می گیرد.این قوانین معمولاً به شکل زیر بیان می شود:
اگر( متغیر ) ( حالت ) است، آنگاه ( عملکرد ).

برای مثال ،یک دستگاه تنظیم کننده درجه حرارت را در نظر بگیرید که قانون منطق فازی را می توان اینگونه برایش تعریف کرد:
● اگر ( درجه حرارات) ( بسیار سرد) است، آنگاه ( فن را متوقف کن ).
● اگر درجه حرارت سرد است، آنگاه سرعت فن را کم کن.
● اگر درجه حرارت متعادل است، آنگاه همین سرعت فن را حفظ کن.
به طورکلی روش کار منطق فازی را می توان به شکل زیر نشان داد:

منطق کلاسیک

کاربرد هوش مصنوعی

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

قاعده Soft Computing

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

در واقع بر همین مبناست که منطق فازی به خوبی نشان می دهد که چرا منطق دو ارزشی < صفر و یک > در ریاضیات کلاسیک، قادر به تبیین و توصیف مفاهیم نادقیقی همچون < گرما و سرما> که مبنای بسیاری از تصمیم گیری های هوشمند را تشکیل می دهند ، نیست.
این در حالیست که نحوه استنتاج سیستم های هوشمند با استفاده از منطق فازی، به سرعت باعث پیشرفت این علم شد و باعث شد تا هوش مصنوعی ،حقیقتاً در جهشی فوق العاده ،به هوش انسانی نزدیک تر گردد.

زمینه های کاربرد منطق فازی درهوش مصنوعی

● هوش مصنوعی رویداد گرا: در این نوع، سیستم بر اساس هر رویدادی که انجام می شود، یک واکنش هوشمندانه انجام می دهد. در این حالت با استفاده از قواعد IF/THEN فازی، می توان برای حالات و رویدادهای جزء شده و طبقه بندی شده ،عکس العمل مناسبی تعیین کرد.
● هوش مصنوعی هدف گرا: این نوع هوش مصنوعی،هدف با ارزش بیشتر را بر می گزیند و آن را با تقسیم به زیرهدفهای کوچکتر، پردازش می کند.
در این نوع هوش نیز با کمک منطق فازی می توان با توجه به درجه عضویت، هدف مورد نظر را انتخاب کرد.

نمونه هایی از کاربرد عملی منطق فازی در هوش مصنوعی

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

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

نتیجه

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

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

منبع

اکتبر 28, 2019/0 دیدگاه /توسط daliri

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

هوش محاسباتی

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

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

روش که از رفتار مورچه‌ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد.

مقدمه

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

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

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

از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دوره‌گرد است. به طوری که انواع الگوریتم کلونی مورچه‌ها برای حل این مسئله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار؛ و لذا با گذر زمان می‌تواند جواب را به طور زنده تغییر دهد؛ که این خاصیت در روتینگ شبکه‌های کامپیوتری و سامانه حمل و نقل شهری مهم است.
در مسئله فروشنده دوره گرد باید از یک شهر شروع کرده، به شهرهای دیگر برود و سپس به شهر مبدأ بازگردد بطوریکه از هر شهر فقط یکبار عبور کند و کوتاهترین مسیر را نیز طی کرده باشد. اگر تعداد این شهرها n باشد در حالت کلی این مسئله از مرتبه (n-1)! است که برای فقط ۲۱ شهر زمان واقعاً زیادی می‌برد:

روز۱۰۱۳*۷/۱ = S۱۰۱۶*۴۳۳/۲ = ms۱۰*۱۰۱۸*۴۳۳/۲ =!۲۰

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

مسئله فروشنده دوره گرد

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

<تبخیر شدن فرومون> و <احتمال-تصادف>به مورچه‌ها امکان پیدا کردن کوتاهترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه‌سازی می‌شوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره‌ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره‌ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه‌ها می‌توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.

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

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

۱. مسیر یابی داخل شهری و بین شهری.

۲. مسیر یابی بین پست‌های شبکه‌های توزیع برق ولتاژ بالا.

۳. مسیر یابی شبکه‌های کامپیوتری. ۴-استفاده ازوب. ۵-استفاده ازACOدربهینه سازی شبکه‌های توزیع آب و…

الگوریتم

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

انواع مختلف الگوریتم بهینه‌سازی مورچگان

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

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

۲- سیستم مورچه ماکسیموم – مینیمم: یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد می‌کند و تمام گره‌های مجاور ان به مقدار فرمون بیشینهمقدار دهی اولیه می‌شوند.

۳- سیستم کلونی مورچه: که در بالا توضیحات کافی داده شده است.

۴- سیستم مورچه بر اساس رتبه: تمام راه حل‌های بدست آماده بر اساس طول جواب رتبه‌بندی می‌شوند و بر اساس همین رتبه‌بندی مقدار فرمون آزاد سازی شده توسط آنها مشخص خواهد شد و راه حل با طول کمتر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد می‌کند.

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

منبع

انسان هميشه براي الهام گرفتن به جهان زنده پيرامون خود نگريسته است. يکي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوينچي(1519-1452) طرحي از يک ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشين پرنده اي ساخت که داراي موتور بود و بجاي بال از ملخ استفاده مي کرد.

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

الگوريتم کلونی مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد.

عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

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

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

در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازيست.

جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم :

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

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

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

بهينه سازي مسائل به روش کلونی مورچه ها (ACO) :

همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط 21 شهر زمان واقعا زيادي مي برد:

روز1013*7/1 = S1016*433/2 = ms10*1018*433/2 = !20

با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.

مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

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

همانطور که در شکل 1-1 مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل 2-1) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA مي آيد و بهC مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.

نکه بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED عبور خواهند کرد بلکه تنها مي توان گفت که مثلا 90% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.

نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

1-1

2-1

3-1

4-1

مزيت هاي ACO :

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

کاربردهاي ACO :

از کاربردهاي ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :

1. مسير يابي داخل شهري و بين شهري
2. مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا

3. مسير يابي شبکه هاي کامپيوتري

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

اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.

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

منبع

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

اکتبر 23, 2019/0 دیدگاه /توسط daliri

تشخیص هویت زیست سنجی و بیومتریک قسمت 4

تشخیص هویت زیست سنجی

چكيده

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

1- مقدمه

يكي از اساسي ترين مسايل در خدمات الكترونيك و تأمين امنيت در فرآيندهاي الكترونيكي، جلوگيري از دسترسي غيرمجاز به داده ها و اطلاعات است كه اين دسترسي نامجاز معمولاً با اهدافي همچون نفوذ به سيستم ها، شنود غيرقانوني، وقفه در انتقال اطلاعات، تخريب، تغيير و حذف داده ها به منظور بي اعتبارسازي اطلاعات يا ايجاد خلل در ارايه خدمات الكترونيك صورت مي گيرد. بنابراين از آن جا كه چالش اصلي در خدمات الكترونيك و تأمين امنيت اطلاعات در شبكه هاي رايانه اي، اطمينان كافي از دسترسي فرد مجاز و در زمان هاي مجاز به اطلاعات است فرآيند تصديق هويت امن و روش هاي احراز آن از مهم ترين مسايل در برقراري امنيت به حساب مي آيد.
تاكنون روش ها و تجهيزات بسيار مختلفي براي بررسي و شناسايي هويت كاربران، پيشنهاد گرديده است كه در مراكز زيادي نيز مورد استفاده قرار گرفته اند اما متأسفانه هر كدام از اين روش ها داراي معايبي هستند كه موجب كاركرد نادرست آن ها شده است. از اين رو، انتخاب شيوه مناسبي كه علاوه بر احراز هويت كاربران در كوتاهترين زمان ممكن، بتواند امنيت لازم را در سيستم هاي الكترونيكي تضمين نمايد همواره به عنوان يك مسئله اساسي مطرح بوده است.
يكي از روش هايي كه با استفاده از آن سعي مي شود تا با احراز هويت كاربران و جلوگيري از دسترسي افراد نامجاز به داده ها، قابليت اطمينان به اطلاعات همچنان حفظ گردد، بهره گيري از فناوري زيست سنجی براي شناسايي كاربران در هنگام دسترسي به سيستم هاي اطلاعاتي مي باشد.

2- فناوري زيست سنجی

استفاده از خصوصيات فيزيولوژيكي يا رفتاري فرد و تحليل آن به منظور شناسايي آن فرد كه تحت عنوان فناوري زيست سنجی شناخته مي شود به نوع خاصي از روش هاي امنيتي گفته مي شود كه در آن براي كنترل دسترسي و برقراري امنيت، از خواص قابل اندازه گيري بدن انسان يا هر موجود زنده ديگري استفاده مي شود. همان گونه كه از كلمه زيست سنجی برمي آيد در اين روش با استفاده از الگوريتم هاي رياضي، برداشت هاي ثابت و يكتايي از اندام هاي بدن مي شود كه مي توان از آن به عنوان يك كلمه عبور يكسان و غيرقابل تغيير استفاده كرد. بنابراين در روش زيست سنجی، از ويژگي هاي فيزيولوژيكي يا رفتاري يك شخص براي شناسايي و تأييد خودكار هويت او در سيستم استفاده مي شود كه يا نيازمند تماس فيزيكي مستقيم شخص با يك پويشگر زيست سنجشي است (مانند اثر انگشت) و يا به تماس فيزيكي فرد با پويشگر نيازي نيست (مانند شكل صورت، اجزاي چهره، تن صدا و …).
معمولاً ويژگي هاي انسان ها براي آن كه بتواند در فناوري زيست سنجی مورد استفاده قرار گيرد، با 9 پارامتر مورد ارزيابي قرار مي گيرد كه عبارتند از:

* عموميت: هر شخص داراي آن ويژگي باشد.
* يكتايي: چه تعداد نمونه متفاوت را مي توان تفكيك كرد.
* دوام: معياري براي سنجش آن كه يك ويژگي، چه مدت عمر مي كند.
* قابليت ارزيابي: سهولت استفاده براي ارزيابي نمونه هاي متفاوت؛
* كارايي: دقت، سرعت و پايداري روش مورد استفاده؛
* مقبوليت: ميزان پذيرش تكنولوژي؛
* جايگزيني: سهولت در استفاده از جايگزيني؛
* تصديق هويت: در تصديق هويت، مشخصه يك فرد به پايگاه اطلاعات ارسال مي شود و هدف، بررسي آن به منظور تصديق هويت آن فرد مي باشد كه پاسخ سيستم، الزاماً مثبت يا منفي است.
* تشخيص هويت: در سيستم هاي تشخيص هويت، مشخصه زيست سنجی فرد به سيستم ارايه مي شود و سيستم با جستجوي پايگاه اطلاعات، مشخصات فرد را در صورت موجود بودن استخراج مي كند.

براي اين كه يك ويژگي بدن بتواند به عنوان يك وسيله اندازه گيري مطرح شود بايد شرايط خاصي داشته باشد، به عنوان مثال، بايد ثابت باشد. به همين خاطر نمي توان رنگ مو يا وزن را به عنوان يك خاصيت زيست سنجی در نظر گرفت زيرا به طور دايم در حال تغيير و تبديل هستند. در ضمن، خواص انتخاب شده مي بايست نشان دهنده يك انسان خاص بوده و همچنين به سهولت قابل دسترسي باشد يعني بررسي آن نياز به زحمت زيادي نداشته باشد.
به طور كلي، ويژگي هاي زيست سنجی را مي توان به 2 دسته تقسيم نمود:

1. خصوصيات وابسته به فيزيك انسان ها: اين دسته از ويژگي ها به مجموعه اي از خصوصيات همراه انسان اعم از اثر انگشت، عنبيه چشم، چهره، DNA و … اشاره دارد. اين ويژگي ها از بدو تولد انسان و گاهي قبل از تولد، شروع به شكل گيري نموده و تا آخر عمر، به طور ثابت و غيرقابل تغيير در بدن انسان باقي مي مانند.
2. خصوصيات رفتاري انسان ها: اين دسته از ويژگي ها در حقيقت، خصوصيات ناشي از رفتارهاي انسان هاست، همانند چگونگي راه رفتن، نحوه فشردن دكمه ها (مثلاً تلفن همراه) و … كه مي تواند بيانگر مشخصات يك انسان خاص باشد، مانند راه رفتن يك انسان كه گاهي با نگاه كردن آن از پشت سر مي توان تشخيص داد كه وي كدام شخص است.

3- مزاياي استفاده از سيستم هاي امنيتي زيست سنجی

با استفاده از روش هاي زيست سنجی مي توان تقريباً مطمئن شد همان كسي كه انتظارش مي رود، به امكانات و منابع دسترسي دارد. براي مثال، اثر انگشت، همواره يكتا و يكسان است و مشكلاتي مانند فراموش كردن رمز عبور يا گم كردن آن در اين روش وجود ندارد، سرعت بسيار بالايي دارد و براي كاربران عادي نياز به آموزش نمي باشد، امكان سرقت دستگاه هاي زيست سنجی نيز بسيار كم است يا در پاره اي از مواقع، صفر مي باشد. تمام اين مزايا باعث شده است كه امروزه براي تأمين امنيت اكثر سيستم هاي رايانه اي و مبتني بر شبكه، به طور گسترده اي از روش هاي زيست سنجی استفاده شود. البته سيستم هاي زيست سنجی داراي معايب خاص خودشان هستند اما به دليل مزاياي بسيار زيادي كه نسبت به روش هاي سنتي شناسايي افراد دارند، استفاده از آن ها روز به روز در حال افزايش است.

4- معايب استفاده از فناوري زيست سنجی

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

5- روش هاي تعيين هويت در فناوري زيست سنجی و بررسي نقاط ضعف آنها

روش هاي متنوعي براي تعيين هويت زيست سنجی وجود دارد، مانند تعيين هويت از طريق اثر انگشت، بررسي دقيق كف دست، رگ هاي كف دست، كنترل شبكيه چشم، تعيين كنترل رگ هاي چشم، هندسه صورت، امضا، صدا، عنبيه چشم، راه رفتن، تعيين هويت از طريق چهره و … كه در زير به بيان مزايا و مشكلات هر يك از آن ها مي پردازيم.

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

تعيين هويت افراد با استفاده از اثر انگشت، نسبت به ساير روش هاي زيست سنجی تعيين هويت به طور گسترده اي مورد استفاده قرار مي گيرد. امروزه از اثر انگشت در صنايع رايانه اي مانند كنترل لايسنس نرم افزارها، ورود به شبكه و سيستم ها و مواردي همچون بازكردن درب اتومبيل، روشن كردن خودرو، بازكردن قفل گاو صندوق و درب ها به طور گسترده اي استفاده مي شود. بزرگترين دليل استفاده گسترده و عمومي از اثر انگشت به عنوان ابزار تعيين هويت اين است كه اثر انگشت افراد، منحصر به فرد بوده و در طول عمر شخص تغيير نمي كند.

اولين استفاده از اثر انگشت در مسايل تشخيص هويت به حدود سال 1900 برمي گردد. در ابتدا براي تشخيص يك اثر انگشت از ديگري سعي در تطبيق خطوط آن بود كه به علت وجود خطاي انساني، معمولاً شامل خطاهايي در اين زمينه است. براي رفع اين مشكل، دستگاه هايي براي تشخيص اثر انگشت ايجاد شدند. از ابتدايي ترين اين دستگاه ها مي توان به دستگاه هاي حسگر اثر انگشت نوري اشاره كرد كه در حدود سال 1970 طراحي گرديدند كه بر اساس بازتابش داخلي كار مي كردند. به اين معني كه منبع نور، به سطح شيشه اي كه انگشت روي آن قرار داشت تابيده شده و بازتابش آن جذب مي شود. مقدار اين نور بازتابيده شده بستگي به عمق شيارهاي سطح پوست و بيشترين بازتابش، مربوط به سطح در تماس پوست با شيشه است. مزاياي اين طرح عبارتند از صرف زمان اندك براي شناسايي، مقاوم بودن در مقابل تداخل الكترواستاتيكي و قيمت ارزان علاوه بر وضوح خوب كه در مقابل معايبي همچون اندازه بزرگ دستگاه، امكان جعل بالا و پيچيدگي هاي به كار رفته، قرار دارند.

دستگاه هاي ديگري كه براي ثبت اثر انگشت طراحي گرديدند داراي حسگرهايي از نوع حالت جامد، مانند حسگر اثر انگشت گرمايي بودند. اين نوع حسگرها از تفاوت گرمايي بين شكاف ها و برآمدگي هاي اثر انگشت به عنوان پارامتري تعيين كننده استفاده مي كنند. بدين معني كه جاهايي از پوست دست (برآمدگي ها) كه در تماس با سطح حسگر مي باشند، تفاوت گرمايي را نسبت به نقاطي كه در تماس نيستند (شيارها) احساس مي كنند. مزاياي اين حسگر نيز حجم كم دستگاه، ارزان بودن و امكان يكپارچگي آن ها مي باشد كه البته معايبي چون توان مصرفي بالا، دقت پايين و تأثيرپذيري از دماي محيط را هم دارند.
از حدود سال 1997، استفاده از دانش MEMS در حسگرهاي اثر انگشت آغاز گرديد كه تاكنون چند نمونه از دستگاه هايي كه با اين نوع از حسگرها طراحي و ساخته شده اند روانه بازار گرديده اند كه آخرين نمونه آن ها در سال 2008 ارايه گرديد.در اين دستگاه ها از نوعي حسگر به نام حسگرهاي خازني استفاده شده است كه بر پايه تغييرات خازني كار مي كنند و شامل دو صفحه فلزي مي باشند كه نقش الكترودهاي خازن را دارند. براي ايجاد تغييرات خازني، يكي از صفحه ها بسته به نوع نياز، متحرك و ديگري ثابت است. صفحه متحرك كه ديافراگم ناميده مي شود بر اثر اعمال فشار خارجي جابه جا شده و باعث كم شدن فاصله هوايي بين الكترودهاي خازن گرديده و تغييرات خازني را موجب مي شود.

در حسگرهاي خازني مورد استفاده در حسگر اثر انگشت، صفحه بالايي به عنوان ديافراگم در نظر گرفته مي شود كه بر اثر فشار اعمالي بر اثر تماس با سطح پوست دست (برآمدگي هاي سطح پوست انگشت) جابه جا مي شود. از عوامل مؤثر در عملكرد حسگرهاي اثر انگشت MEMS مي توان مواردي همچون ابعاد ديافراگم، ساختار خازن، مواد تشكيل دهنده ديافراگم كه باعث حساسيت خيلي زياد حسگرها مي شود و همچنين اندازه، شكل و ضخامت ديافراگم را بيان نمود و از آن جا كه ساختار حسگر انگشت بر پايه ساختار اين خازن ها بنا نهاده شده است، با افزايش حساسيت مكانيكي و الكتريكي اين خازن ها، حساسيت حسگر اثر انگشت نيز بهبود پيدا مي كند.

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

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

استفاده از روش هاي زيست سنجی در فرآيند تصديق هويت از طريق اثر انگشت، داراي چندين نقطه ضعف عمده مي باشد كه در زير به برخي از آن ها اشاره مي شود:

* جعل ورودي: يكي از رايج ترين حملات موجود در سيستم هاي تصديق هويت زيست سنجی مانند اثر انگشت، جعل ورودي يا وارد كردن يك ورودي به جاي ورودي واقعي مي باشد. اين حمله ساده ترين راهكار براي يك مهاجم است تا بتواند با اثر انگشت مصنوعي و ساختگي، فرآيند تصديق هويت را انجام دهد.

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

* كيفيت پايين ورودي: تكنيك هاي تطابق اثر انگشت به 2 صورت ممكن است انجام گيرند: بر پايه جزييات يا بر اساس همبستگي. در تكنيك هاي ويژگي محور، ابتدا نقاط يا ويژگي ها مشخص مي شود و سپس محل نسبي آن روي انگشت نگاشت مي شود. زماني كه كيفيت پايين باشد استخراج دقيق نقاط ويژگي مشكل مي باشد.

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

* تغيير در پايگاه داده زيست سنجی: اولين مرحله در سيستم هاي تشخيص بيومتريك، ذخيره نمونه هاي منحصر به فرد به منظور استفاده از آن ها در فرآيند تصديق هويت مي باشد. در اكثر سيستم ها يك پايگاه داده براي ذخيره اين نمونه ها در نظر گرفته مي شود. فرآيندي كه كاربر براي اولين بار در آن اقدام به ثبت اثر انگشت مي كند، فرآيند ثبت نام دارد.
* تغيير در استخراج كننده ويژگي ها: استخراج كننده ويژگي يكي از بخش هاي سيستم تشخيص زيست سنجی است كه ممكن است اين بخش توسط مهاجم مورد حمله قرار گرفته و كاركرد آن را تغيير يابد. مهاجم با ربودن تصاوير اثر انگشت از پايگاه داده، نمونه هاي تقلبي خود را جايگزين آن ها مي كند. در اين صورت، سيستم هنگام تشخيص نمونه ها، يك اثر انگشت معتبر را رد و يك اثر انگشت نامعتبر را تأييد مي كند.

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

مشكلات عملي زيادي در سيستم هاي شناسايي اثر انگشت وجود دارد. مثلاً هر دفعه كه يك اثر انگشت گرفته مي شود، ممكن است به خاطر قابليت كشساني پوست، تحريف هايي در شكل و محل اثر انگشت ايجاد شود. علاوه بر اين، اطمينان بالا و پردازش بلادرنگ، فاكتورهاي مهم مورد نياز در سيستم خودكار شناسايي اثر انگشت هستند.

از ديگر روش هايي كه امروزه در فناوري زيست سنجی از آن استفاده مي شود انجام برخي از حركات يا رفتارهاي خاص بر روي تجهيزات جمع آوري كننده اطلاعات مي باشد. از نمونه هاي اين روش مي توان به دستگاه هايي اشاره كرد كه از كاربر مي خواهد تا با دست خويش، عمل خاصي را انجام داده يا شكل مشخصي را در صفحه ثبت كننده اطلاعات، ترسيم نمايد. اندازه گيري و ثبت ويژگي هايي همچون اندازه، طول، سرعت، شتاب، انحنا، ميزان فشار وارده، دامنه لرزش اعضاي حركتي بدن، درجه حرارت بدن و … و مقايسه آن ها با اطلاعات از قبل ثبت شده، از كاركردهاي اين دستگاه ها مي باشد. از مشكلات خاص اين روش نيز مي توان به عدم بهره گيري از آن ها در هنگام بيماري افراد در روش ايي كه نيازمند انجام حركات رفتاري خاص هستند يا آموختن بعضي از روش هاي اجرايي حركات و رفتارها اشاره نمود.

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

پس از ثبت داده زيست سنجی توسط عامل هوشمند، براي اين كه اطمينان حاصل گردد نمونه هاي جمع آوري شده داراي كمترين مقدار تيرگي و نويز هستند، عمل پيش پردازش روي آن ها انجام مي گيرد. سپس بررسي زنده بودن نمونه ثبت شده توسط عامل هوشمند، اولين آزمايشي است كه روي نمونه انجام مي شود. اين كار، براي جلوگيري از به كارگيري روش هاي جعلي در تصديق هويت صورت مي گيرد. پس از عمليات مقداردهي اوليه، اين نمونه هاي جمع آوري شده با نمونه هاي موجود در پايگاه هاي داده سرورهاي زيست سنجی كه به صورت رمزشده ذخيره شده اند، تطبيق داده مي شود. اگر در هر لحظه از زمان، آزمايش هاي صورت پذيرفته با موفقيت همراه نباشد فوراً خدمات الكترونيك متوقف شده و نتيجه به ارايه كنندگان آن خدمات اطلاع داده خواهد شد. اين فرآيند در تمام مدت زمان ارايه خدمات الكترونيك انجام مي گيرد.

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

منبع

تشخیص هویت زیست سنجی و بیومتریک قسمت 1
تشخیص هویت زیست سنجی و بیومتریک قسمت 2
تشخیص هویت زیست سنجی و بیومتریک قسمت 3
تشخیص هویت زیست سنجی و بیومتریک قسمت 4
تشخیص هویت زیست سنجی و بیومتریک قسمت 5

اکتبر 22, 2019/0 دیدگاه /توسط daliri

ربات چیست؟ قسمت 2

آموزش های عمومی هوش مصنوعی

تاریخچه تحولات حوزه رباتیک

1920: نمایش نامه نویس چک اسلواکی Karl capek، کلمه ربات را در نمایش«‌ربات‌های جهانی روسیه» استفاده کرد این جمله از کلمه چکی « Robota» به معنی« کوشش ملال آور‌» آمده است.
1938: نخستین الگوی قابل برنامه‌ریزی که یک دستگاه سم‌پاشی بود، توسط دو آمریکایی به نام‌های Willard pollard و Harold Roselund برای شرکت devilbiss طراحی شد.
1942: ایزاک آسیموفRunaround را منتشر کرد و در آن قوانین سه‌گانه رباتیک را تعریف کرد.

1946: ظهور کامپیوتر: George Devol، با استفاده از ضبط مغناطیسی، یک دستگاه playback همه منظوره، برای کنترل ماشین به ثبت رساند. John Mauchly اولین کامپیوتر الکترونیکی (ENIAC) را در دانشگاه پنسیلوانیا ساخت. در MIT، اولین کامپیوتر دیجیتالی همه منظوره (Whirl wind) اولین مسئله خود را حل کرد.
1951: در فرانسه Reymond Goertz اولین بازوی مفصلی کنترل از راه دور را برای انجام مأموریت هسته‌ای طراحی کرد. طراحی آن مبتنی بر کلیه روابط متقابل مکانیکی بین بازوی اصلی و فرعی با استفاده از روش متداول تسمه و قرقره بود که نمونه‌هایی برگرفته از این طرح هنوز هم در مواردی که نیاز به لمس نمونه‌های کوچک هسته‌ای است، دیده می‌شود.
1954: George Devol اولین ربات قابل برنامه‌ریزی را طراحی و عبارت جهانی اتوماسیون را ابداع کرد. این امر زمینه‌ای برای نام‌گذاری این شرکت به Unimation در آینده شد.
1959: Marvin Minsky و John McCarthy آزمایشگاه هوش مصنوعی را در MIT بنا نهادند.

1960: Unimation توسط شرکت Coudoc خریداری شد و توسعه سیستم ربات‌های آن آغاز گردید. کارخانجات ساخت تراشه مانند AMF پس از آن شناخته شدند و اولین ربات استوانه ای شکل به نام Versatran که توسط Harry Johnson&Veljkomilen kovic طراحی شده بود، فروش رفت.
1962: جنرال موتورز اولین ربات صنعتی را از Unimation خریداری کرد و آن را در خط تولید خود قرار داد.
1963: John Mccarthy آزمایشگاه هوش مصنوعی دیگری از دانشگاه استنفورد بنا کرد.
1964: آزمایشگاه‌های تحقیقاتی هوش مصنوعی در M.I.T ،مؤسسات تحقیقاتی استنفورد (SRI)، دانشگاه‌ استنفورد و دانشگاه ادین برگ گشایش یافت.
1964: رباتیک C&D پایه گذاری شد.
1965: دانشگاه Carnegie Mellon مؤسسه رباتیک خود را تأسیس کرد.

1965: حرکت یکنواخت ( Homogeneous Trans formation) در شناخت نحوه حرکات ربات به کار رفت. این روش امروزه به عنوان نظریه اسامی رباتیک وجود دارد.
1965: ژاپن ربات Verstran ( نخستین رباتی که به ژاپن وارد شد) را از AMF خریداری کرد.
1968: کاوازاکی مجوز طراحی ربات‌های هیدرولیک را از Unimation گرفت و تولید آن را در ژاپن آغاز کرد.
1968: SRI،Shakey (یک ربات سیار با قابلیت بینایی و کنترل با یک کامپیوتر به اندازه یک اتاق) را ساخت.
1970: پروفسور victor sheinman از دانشگاه استنفورد بازوی استاندارد را طراحی کرد. ساختار ترکیب حرکتی او هنوز هم به بازوی استاندارد معروف است.
1973: Cincinnate Milacron اولین مینی کامپیوتر قابل استفاده تجاری که با رباتهای صنعتی کنترل می شد(T3) را عرضه کرد. ( طراحی توسطRichard Hohn )
1974: پروفسور Victor Scheinman، سازنده بازوی استاندارد، Inc Vicarm را جهت فروش یک نسخه برای کاربردهای صنعتی ساخت. بازوی جدید با یک مینی کامپیوتر کنترل می‌شد.
1976: Vicarm Inc در کاوشگر فضایی وایکینگ 1و2 استفاده شد. یک میکرو کامپیوتر هم در طراحی vicarm به کار رفت.

1977: یک شرکت ربات اروپایی (ASEA)، دو اندازه از ربات‌های قدرتمند الکتریکی صنعتی را عرضه کرد که هر دو ربات از یک کنترلر میکرو کامپیوتر برای برنامه ریزی عملکرد خود استفاده می‌کردند.
1977: Inc, Unimation vicarm را فروخت.
1978: unimation با استفاده از تکنولوژی Vicarm ‌ ( puma) ماشین قابل برنامه‌ریزی برای مونتاژ( puma) را توسعه داد . امروزه همچنان می‌توان puma را در بسیاری از آزمایشگاه‌های تحقیقاتی یافت.
1978: ماشین خودکار Brooks تولید شد.
1978: IBM و SANKYO ربات با بازوی انتخاب کننده، جمع کننده و مفصلی (SCARA) که در دانشگاه Yamanashi ژاپن برنامه‌ریزی و تولید شده بود، را فروختند.
1980: Cognex تولید شد.

1981: گروه ربات‌های CRS عرضه شد.
1982: Fanuc از ژاپن و جنرال موتورز درGM Fanuc برای فروش ربات در شمال آمریکا قرار داد بستند.
1983: تکنولوژی Adept عرضه شد.
1984: Joseph Engelberger ایجاد تغییرات در رباتیک را آغاز کرد و پس از آن نام ربات‌های کمکی (Helpmate) به ربات‌های خدماتی توسعه یافته (developed service Robots) تغییر یافت.
1986: با خاتمه یافتن مجوز ساخت Unimation، کاوازاکی خط تولید ربات‌های الکتریکی خود را توسعه داد.
1988: گروه Staubli، Unimation را از Westing house خرید.
1989: تکنولوژی Sensable عرضه شد.

1994: یک ربات متحرک شش پا از مؤسسه رباتیک CMUیک آتشفشان در آلاسکا را برای نمونه‌برداری از گازهای آتشفشانی کاوش کرد.
1997: ربات راه‌یاب مریخ ناسا از زمانی‌که ربات وارد مریخ شد تصاویری از جهان را ضبط و ربات سیار Sojourner تصاویری از سفرهایش به سیاره‌های دور را ارسال کرد.
1998: Honda نمونه ای از p3 (هشتمین نمونه در پروژه طراحی شبیه انسان ) که در 1986 آغاز شده بود را عرضه کرد.
2000: Honda نمونه آسیمو نسل بعدی از سری ربات‌های شبیه انسان را عرضه کرد.

2000: Sony از ربات شبیه انسان خود که لقب SDR ( Sony Dream Robots) را گرفت، پرده برداری کرد.
2001: Sony دومین نسل از ربات‌های سگ Aibo را عرضه کرد.
2001: سیستم کنترل از راه دور ایستگاه فضایی(SSRMS ) توسط مؤسسه رباتیک MD در کانادا ساخته و با موفقیت به مدار پرتاب شد و عملیات تکمیل ایستگاه فضایی بین‌المللی را آغاز کرد.

منبع

تاریخچه ربات

كلمه‌ ربات‌ بعد از به‌ صحنه‌ درآمدن‌ یك‌ نمایش‌ در سال‌1920 میلادی‌ در فرانسه‌ متداول‌ و مشهور گردید. در این‌ نمایش‌ كه‌ اثر«كارل‌ كپك‌» بود، موجودات‌ مصنوعی‌ شبیه‌ انسان‌، وابستگی‌ شدیدی‌نسبت‌ به‌ اربابان‌ خویش‌ از خود نشان‌ می‌دادند. این‌ موجودات‌ مصنوعی‌شبیه‌ انسان‌ در آن‌ نمایش‌، ربات‌ نام‌ داشتند.
در حال‌ حاضر ربات‌هایی‌ را كه‌ در شاخه‌های‌ مختلف‌ صنایع‌ مورداستفاده‌ می‌باشند، می‌توان‌ به‌ عنوان‌ «ماشین‌های‌ مدرن‌، خودكار، قابل‌هدایت‌ و برنامه‌ریزی‌»تعریف‌ كرد. این‌ ربات‌ها قادرند در محل‌های‌متفاوت‌ خطوط تولید، به‌ طور خودكار، وظایف‌ گوناگون‌ تولیدی‌ را تحت‌یك‌ برنامه‌ از پیش‌ نوشته‌ شده‌ انجام‌ دهند.

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

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

– برای‌ اضافه‌ كاری‌ این‌ ربات‌ها، هزینه‌ اضافی‌ پرداخت‌ نمی‌شود.حق‌ بیمه‌، حق‌ مسكن‌ و هزینه‌ ایاب‌ و ذهاب‌ پرداخت‌ نمی‌شود. احتیاج‌ به‌افزایش‌ حقوق‌ ندارند و هزینه‌این‌ نیز از بابت‌ بهداشت‌ و درمان‌ بر واحدتولیدی‌ تحمیل‌ نمی‌كنند.
ویژگی‌های‌ ذكر شده‌ سبب‌ می‌شوند كه‌ سهم‌ هزینه‌ كار مستقیم‌ نیروی‌انسانی‌ در هزینه‌ محصولات‌ تولیدی‌، واحدهای‌ تولیدی‌ كاهش‌ پیداكند.

ربات چیست؟

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

“یک ربات هوشمند ،ماشین خودکار چند منظوره ای است که طیف وسیعی از وظایف متفاوت را، تحت شرایطی که حتی ممکن است به آن شناخت کافی نداشته باشد ،همانند انسان آن را انجام دهد”
موسسه صنعتی آمریکا RAI یا Robotic Industrial Association که شرکتی با سابقه در صنعت رباتیک می باشد و در تولید بازوهای ربات های صنعتی یا (Manipulators) است، این گونه ربات را تعریف می کند:
“یک ربات، یک جابجا کننده چند وظیفه ای برنامه پذیر است که برای حرکت دادن مواد ، قطعات ،ابزار ها یا وسایل خاص ،با استفاده از حرکات برنامه ریزی شده قابل تغییر برای تحقق فرامین مختلف ،طراحی شده است.
ربات در معنای عام تر و کلی تر یک ماشین الکترومکانیکی هوشمند است، با خصوصیات زیر:
1- می توان آن را مکرراً برنامه ریزی کرد.
2- چند کاره است.
3- Multi Tasking
4- کارآمد و مناسب برای محیط است و توانایی هماهنگ کردن خود با محیط را دارد.
و خلاصه ربات ماشینی است که کاری مستمر و تکراری را بدون خستگی و با سرعت بالا و بدون اشتباه (منظور با خطای کم) انجام دهد

کلمه روباتیک (robatics) اولین بار توسط ایزاک آسیموف در یک داستان کوتاه ارائه شد. ایزاک آسیموف (1920-1992) نویسنده کتابهای توصیفی درباره علوم و داستانهای علمی تخیلی است. ایزاک آسیموفRunaround را منتشر کرد و در آن قوانین سه‌گانه رباتیک را تعریف کرد.
هدف رباتیک اتصال هوش از ادراک به رفتار می باشد. رباتیک در اکثر مواقع در حوزه مهندسی برق، مهندسی مکانیک و مهندسی رایانه کاربرد دارد.
کنترل کننده ها اولین هدایت کننده های رباتیک بوده اند. استفاده از تئوری کنترل در هدایت سامانه های پیچیده ، موضوع علم سیبرنیتیک است. چرخه حس، طرح و عمل در هوش مصنوعی توسعه ای از علم سیبرنیتیک برای هدایت هوشمند سیستم ها می باشد، در این چرخه تعریف عمومی تری از خطا بکار رفته است و هدف آن حداقل سازی این خطاست.
در این چرخه حس وظیفه گرفتن اطلاعات از حسگر های ربات تبدیل آن به دانشی درباره جهان ، وظیفه اخذ دانش و حصول آگاهی، استدلال ، تصمیم گیری و تولید اوامری برای اجرا و عمل وظیفه انجام اوامر را بر عهده دارد.

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

1 الکترونیک ( شامل مغز ربات)
2 مکانیک (شامل بدنه فیزیکی ربات)
3 نرم افزار (شامل قوه تفکر و تصمیم گیری ربات)
اگریک ربات را به یک انسان تشبیه کنیم، بخشهایی مربوط به ظاهر فیزیکی انسان را متخصصان مکانیک می سازند
مغز ربات را متخصصان الکترونیک توسط مدارای پیچیده الکترونیک طراحی و می سازند
و کارشناسان نرم افزار قوه تفکر را به وسیله برنامه های کامپیوتری برای ربات شبیه سازی می کنند تا در موقعیتهای خاص ، فعالیت مناسب را انجام دهد.
روباتیک، علم مطالعه فن آوری مرتبط با طراحی، ساخت و اصول کلی و کاربرد روباتهاست. روباتیک علم و فن آوری ماشینهای قابل برنامه ریزی، با کاربردهای عمومی می باشد.
برخلاف تصور افسانه ای عمومی از رباتها به عنوان ماشینهای سیار انسان نما که تقریباً قابلیت انجام هر کاری را دارند، بیشتر دستگاههای روباتیک در مکانهای ثابتی در کارخانه ها بسته شده اند و در فرایند ساخت با کمک کامپیوتر، اعمال قابلیت انعطاف، ولی محدودی را انجام می دهند چنین دستگاهی حداقل شامل یک کامپیوتر برای نظارت بر اعمال و عملکردهای و اسباب انجام دهنده عمل مورد نظر، می باشد. علاوه براین، ممکن است حسگرها و تجهیزات جانبی یا ابزاری را که فرمان داشته باشد بعضی از رباتها، ماشینهای مکانیکی نسبتاً ساده ای هستند که کارهای اختصاصی مانند جوشکاری و یا رنگ افشانی را انجام می دهند. که سایر سیستم های پیچیده تر که بطور همزمان چند کار انجام می دهند، از دستگاههای حسی، برای جمع آوری اطلاعات مورد نیاز برای کنترل کارشان نیاز دارند. حسگرهای یک ربات ممکن است بازخورد حسی ارائه دهند، طوریکه بتوانند اجسام را برداشته و بدون آسیب زدن، در جای مناسب قرار دهند. ربات دیگری ممکن است دارای نوعی دید باشد.، که عیوب کالاهای ساخته شده را تشخیص دهد. بعضی از رباتهای مورد استفاده در ساخت مدارهای الکترونیکی، پس از مکان یابی دیداری علامتهای تثبیت مکان بر روی برد، می توانند اجزا بسیار کوچک را در جای مناسب قرار دهند. ساده ترین شکل رباهای سیار، برای رساندن نامه در ساختمانهای اداری یا جمع آوری و رساندن قطعات در ساخت، دنبال کردن مسیر یک کابل قرار گرفته در زیر خاک یا یک مسیر رنگ شده که هرگاه حسگرهایشان در مسیر، یا فردی را پیدا کنند متوقف می شوند. رباتهای بسیار پیچیده تر رد محیط های نامعین تر مانند معادن استفاده می شود.
روباتها همانند کامپیوترها قابلیت برنامه ریزی دارند.بسته به نوع برنامه ای که شما به آنها می دهید.کارها وحرکات مختلفی را انجام می دهند.رشته دانشگاهی نیز تحت عنوان روباتیک وجود دارد.که به مسایلی از قبیل سنسورها، مدارات ، فیدبکها،پردازش اطلاعات وبست وتوسعه روباتها می پردازد.روباتها انواع مختلفی دارند از قبیل روباتهای شمشیر باز، دنبال کننده خط،کشتی گیر،
فوتبالیست،و روباتهای خیلی ریز تحت عنوان میکرو روباتها،روباتهای پرنده وغیره نیز وجود دارند.
روباتها برای انجام کارهای سخت ودشواری که بعضی مواقع انسانها از انجام آنها عاجز یا انجام آنها برای انسان خطرناک هستند.مثل روباتهایی که در نیروگاهای هسته ای وجود دارند.،استفاده می شوند.
کاری که روباتها انجام میدهند.، توسط میکرو پروسسرها(microprocessors) و میکروکنترلرها(microcontroller) کنترل می شود.با تسلط در برنامه نویسی این دو می توانید دقیقا همان کاری را که انتظار دارید روبات انجام دهد.
روباتهایی شبیه انسان (human robotic)نیز ساخته شده اند.،آنها قادرند اعمالی شبیه انسان را انجام دهند.حتی بعضی از آنها همانند انسان دارای احساسات نیز هستند.بعضی از آنها شکلهای خیلی ساده ای دارند.آنها دارای چرخ یا بازویی هستند که توسط میکرو کنترلرها یا میکرو پرسسرها کنترل می شوند.در واقع میکروکنترلر یا میکرو پروسسر به مانند مغز انسان در روبات کار می کند.برخی از روباتها مانند انسانها وجانوران خون گرم در برخورد و رویارویی با حوادث ومثایل مختلف به صورت هوشمند از خود واکنش نشان می دهند.یک نمونه از این روباتها روبات مامور است.
برخی روباتها نیز یکسری کارها را به صورت تکراری با سرعت ودقت بالا انجام می دهند مثل روبات هایی که در کارخانه های خودرو سازی استفاده می شوند.این گونه روبات کارهایی از قبیل جوش دادن بدنه ماشین ، رنگ کردن ماشین را با دقتی بالاتر از انسان بدون خستگی و وقفه انجام می دهند.

ربات چیست؟ قسمت 1
ربات چیست؟ قسمت 2
ربات چیست؟ قسمت 3
ربات چیست؟ قسمت 4
ربات چیست؟ قسمت 5
ربات چیست؟ قسمت 6
ربات چیست؟ قسمت 7
ربات چیست؟ قسمت 8

اکتبر 17, 2019/0 دیدگاه /توسط daliri

منطق فازی (Fuzzy Logic) قسمت 2

هوش محاسباتی

منطق فازی (fuzzy logic) چیست؟

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

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

منطق فازی 0 و 1 را به عنوان حالت های مفرط حقیقت (واقعیت) در نظر می گیرند اما چندین حالت درستی نیز در بین این دو حالت قرار می گیرد مثلا نتیجه مقایسه بین دو چیز ممکن است نه کوتاه یا بلند بودن آن ها بلکه 0.38 بلندتر بودن یکی از آن ها باشد.

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

هوش مصنوعی – سیستم های منطق فازی

سیستم های منطق فازی (FLS) در پاسخ به ورودی ناقص، مبهم، تحریف شده و یا غیر دقیق، خروجی قابل قبول ولی مشخصی تولید می کنند.

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

بلوک منطقی متعارفی که کامپیوتر می تواند آن را درک کند یک ورودی مشخص دریافت می کند و یک خروجی معین و قطعی به صورت صحیح یا غلط تولید می کند که در واقع معادل بله و خیر در انسان ها است.

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

قطعا بله
احتمالا بله
نمی توان گفت
احتمالا خیر
قطعا خیر

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

اجرا

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

از این روش می توان در سخت افزار ها، نرم افزار ها و یا ترکیبی از آن ها استفاده کرد.

چرا منطق فازی؟

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

معماری سیستم های منطق فازی

این سیستم دارای 4 بخش اصلی است که در ادامه تشریح خواهند شد:

1. مدول فازی ساز:

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

X عددی مثبت و بزرگ است	LP
X عددی مثبت و متوسط است	MP
X کوچک است	S
X عددی منفی و متوسط است	MN
X عددی منفی و بزرگ است	LN

2. پایگاه دانش:

محلی است که دستورات “اگر- آنگاه” که توسط کارشناسان ایجاد شده اند در آن ذخیره می شود.

3. موتور استنتاج:

در این بخش فرآیند استدلالی انسان به وسیله نتیجه گیری های فازی از ورودی ها و دستورات شرطی شبیه سازی می شود.

4. مدول غیرفازی ساز:

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

توابع عضویت بر روی مجموعه متغیر های فازی عمل می کنند.

تابع عضویت

تابع عضویت به شما اجازه می دهد تا یک واژه زبانی را کمی سازی کرده و یک مجموعه فازی را به صورت نموداری نمایش دهید. یک تابع عضویت برای مجموعه فازی A در دامنه سخن Universe of Discourse) X) به شکل روبرو تعریف می شود: [µA:X →0,1]

در این حالت هر المان از X به مقداری بین صفر و یک نگاشته می شود که به آن مقدار عضویت یا درجه عضویت گفته می شود. این مقدار نمایش کمی درجه عضویت المان موجود در X را نسبت به مجموعه فازی A نشان می دهد.

محور x دامنه سخن را نشان می دهد
محور y درجه عضویت را در بازه صفر تا یک نمایش می دهد.

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

همه توابع عضویت برای LP, MP, S, MN, و LN در شکل زیر نمایش داده شده اند.

توابع عضویت با شکل مثلثی در میان توابع با شکل های دیگر نظیر ذوزنقه ای ، گاوسی و… متداول ترین هستند.

در اینجا، مقدار ورودی برای فازی ساز پنج مرحله ای از 10- ولت تا 10+ ولت تغییر می کند. به همین دلیل خروجی مربوط به هر ورودی نیز تغییر می کند.

مثالی از سیستم منطق فازی

بیایید یک سیستم تهویه هوا را با سیستم منطق فازی 5 مرحله ای بررسی کنیم. این سیستم دمای سیستم تهویه را به کمک مقایسه دمای اتاق و دمای موردنظر، تنظیم می کند.

الگوریتم

تعریف متغیر های زبانی و عبارت های مربوطه

تعریف توابع عضویت برای آن ها

تشکیل پایگاه دستورات

تبدیل داده های عددی به مجموعه داده های فازی با استفاده از توابع عضویت (فازی سازی)

ارزیابی دستورات موجود در پایگاه دستورات ( موتور استنتاجی)

ترکیب کردن نتایج به دست آمده از هر دستور با سایر نتایج (موتور استنتاجی)

تبدیل داده خروجی به مقادیر غیر فازی (غیر فازی سازی)

توسعه منطق

مرحله 1 : تعریف متغیر ها و عبارت های زبانی

متغیر های زبانی، متغیر های ورودی و خروجی به شکل کلمات و یا جمله های ساده هستند. برای دمای اتاق، سرد، گرم، خیلی گرم و… عبارت های زبانی محسوب می شوند.

دما (t) = {خیلی سرد، سرد، گرم، خیلی گرم، فوق العاده گرم}

هر عضو از این مجموعه یک عبارت زبانی به شمار می رود و می تواند بخشی از مقادیر کلی دمای اتاق را پوشش دهد.

مرحله 2: تعریف توابع عضویت

توابع عضویت متغیر دما در شکل زیر نشان داده شده اند:

مرحله 3: تشکیل پایگاه دستورات

دراین مرحله یک ماتریس از مقادیر دمای اتاق در برابر دمای مطلوب اتاق که یه سیستم تهویه هوا باید آن را تامین کند تشکیل داده می شود .

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

سپس مجموعه ای از دستورات شرطی به فرم “اگر- آنگاه- در غیر این صورت” در پایگاه دستورات تشکیل می شود.

نوع عملکرد	شرط	شماره دستور
افزایش دما	اگر دما= (سرد یا خیلی سرد) و دمای مطلوب = گرم… آنگاه	1
کاهش دما	اگر دما= (خیلی گرم یا فوق العاده گرم) و دمای مطلب = گرم…آنگاه	2
بدون تغییر	اگر دما=( گرم) و دمای مطلوب = گرم… آنگاه	3

مرحله 4: به دست آوردن مقادیر فازی

عملیات مجموعه های فازی ارزیابی دستورات موجود را به عهده می گیرند. عملیات مورد استفاده برای “یا” و “و” به ترتیب Maxو Min هستند. نتایج همه شرایط با یکدیگر ترکیب می شوند تا نتیجه نهایی بدست بیاید. این نتیجه یک مقدار فازی است.

مرحله 5: اجرای عملیات غیرفازی سازی

در نهایت عملیات غیر فازی سازی با توجه به تابع عصویت برای متغیر خروجی انجام می شود.

حوزه کاربرد منطق فازی

سیستم های خودرو:

گیربکس های اتوماتیک

فرمان پذیری چهار چرخ

کنترل محیط زیست وسیله نقلیه

کالا های الکترونیکی:

سیستم های Hi-fi

دستگاه های فتوکپی

دوربین های عکاسی و فیلم برداری

تلویزیون

لوازم خانگی

مایکروویو ها

یخچال ها

توستر ها

جاروبرقی ها

ماشین های ظرف شویی

کنترل کننده های محیطی

سیستم های تهویه هوا

مرطوب کننده ها

نقاط قوت سیستم های منطق فازی

مفاهیم ریاضی با استفاده از استدلال های فازی بسیار ساده هستند.

می توانید یک سیستم منطق فازی را به دلیل انعطاف پذیر بودن منطق فازی با اضافه کردن و یا حذف برخی از قوانین تغییر دهید.

سیستم های منطق فازی می توانند اطلاعات ورودی غیر دقیق، مغشوش و یا نویزدار را دریافت کنند.

ساخت ودرک این سیستم ها بسیار راحت است.

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

نقاط ضعف سیستم های منطق فازی

هیچ رویکرد سیستماتیکی برای طراحی سیستم های فازی وجود ندارد.

درک آن ها تنها در صورتی امکان پذیر است که ساده باشند.

برای مسائلی مناسب هستند که به دقت بالا نیاز ندارند.

منبع

منطق فازی (Fuzzy Logic) قسمت 1
منطق فازی (Fuzzy Logic) قسمت 2

اکتبر 13, 2019/1 دیدگاه/توسط daliri

فشرده سازی تصویر قسمت 1

دسته‌بندی نشده

فشرده سازی تصویر (Image Compression)، کاربردی از فشرده سازی اطلاعات در تصاویر دیجیتال است. هدف از آن کاهش افزونگی (redundancy) محتویات تصویر است برای ذخیره کردن یاانتقال اطلاعات به شکل بهینه.

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

روش‌های فشرده سازی بدون اتلاف عکس‌ها عبارتند از

– کدگذاری بر اساس طولِ ران (run-length encoding)، استفاده شده در روش‌های پیش‌فرض در dcx و یکی از امکانات TIFF ,TGA ,BMP

– entropy coding

– الگوریتم‌های مطابق واژه‌نامه مثل lzw استفاده شده در GIF,TIFF

– کاهش اعتبار (deflation) استفاده شده در TIFF ,MNG ,PNG

روش‌های فشرده سازی پراتلاف عبارتند از

کاهش فضای رنگی

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

chroma subsampling

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

تغییر شکل دادن کدگذاری (transform coding)

این روش بطور عادی بیشترین استفاده را دارد.

fractal compression

بهترین کیفیت عکس در یک نرخ بیت (یا نرخ فشرده سازی) معین هدف اصلی از فشرده سازی عکس است.

به هر حال ویژگی‌های مهم دیگری از رویه‌های فشرده سازی عکس وجود دارد که عبارتند از: ‘

مقیاس پذیری (scability)

به‌طور کلی به کاهش کیفیت حاصل شده در اثر دستکاری گروه بیتی یا فایل گفته می‌شود. (بدون بازیابی). نام‌های دیگر برای مقیاس پذیری،progressive coding یا embedded biststream است. با وجود خلاف واقعی بودنش مقیاس‌پذیری نیز می‌تواند در رمز گذارهای (codec) بدون اتلاف یافت شود. مقیاس‌پذیری خصوصاَ برای پیش نمایش عکس‌ها در حال دریافت کردن آن‌ها یا برای تهیه کیفیت دستیابی متغیر در پایگاه‌های داده مفید است.

انواع مختلف مقیاس پذیری عبارتند از :

کیفیت مترقی(progressive quality)

یا لایه مترقی (layer progressive) گروه بیتی پی در پی عکس را از نو می‌سازد.

وضوح مترقی (progressive resoloution)

ابتدا یک عکس وضوح پایین را کدگذاری می کند سپس تفاوت‌های وضوح بالاتر را کدگذاری می‌کند.

مؤلفه مترقی (progressive component)

ابتدا رنگ را کدگذاری می‌کند.

ناحیه

جذاب کدگذاری (region of interest coding) نواحی خاصی از عکس باکیفیت بالاتری نسبت به سایر نقاط کد گذاری می‌شوند و می‌تواند با مقیاس‌پذیری (کدگذاری ابتدایی یک بخش و دیگران بعداً) ترکیب شود.

اطلاعات

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

قدرت

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

کیفیت

روش فشرده سازی اغلب به وسیلهٔ سیگنال ماکزیمم به نسبت پارازیت (peak signal-to-noise ratio) اندازه‌گیری می شوند. اندازه پارازیت‌ها نشان دهند؟ فشرده سازی پراتلاف عکس است به هر حال قضاوت موضوع گرایانه بیننده همیشه بیان کنند؟ اهمیت اندازه‌گیری است.

Jpeg2000

Jpeg2000 یک استاندارد فشرده سازی عکس براساس wavelet (wavelet-based) است؛ و در سال 2000 به‌وسیله کمیته Joint Photographic Experts Group با نیت جایگزین کردن با استاندارد اصلیJpegکه براساس تغییر گسسته(discrete cosine transform-based) است (محصول سال1991) تولید شده‌است. jpeg2000 زمان بیشتری را برای عملیات باز کردن فشردگی نسبت به JPEG طلب می‌کند.

اثبات از بالا به پایین محصولات فشرده سازی JPEG 2000: شماره‌ها نشان‌دهنده ضریب تراکم استفاده شده‌است.برای مقایسه بهتر شکل بدون مقیاس را نگاه کنید. محصولات JPEG 2000 به فرم JPEG متفاوت به نظر می‌رسند و یک جلوه صیقلی روی عکس وجود دارد و برای نمایان شدن سطوح فشرده سازی بالاتری اختیار می کنند. اغلب یک عکس گرفته شده می‌تواند به اندازه اندازه فایل اصلی خود(bitmapفشرده نشده) بدون متحمل شدن اثر نمایان شدن فشرده شوند

منبع

فشرده سازی با اتلاف داده و بدون اتلاف داده

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

فشرده سازی بدون اتلاف داده

روش‌های کمی برای فشرده سازی بدون اتلاف داده وجود دارد. روش اولکدگذاری طول اجرا (run-length encoding) است که برای فایل‌های BMP استفاده می‌شود. این روش داده‌های متوالی با مقادیر یکسان را می‌گیرد و آن‌ها را با یک متغیر count که بیانگر طول داده‌های یکسان است، ذخیره می‌کند. این روش برای فایل‌های گرافیکی مناسب است زیرا مقادیر داده یکسان بسیاری دارند.

روش دیگر فشرده سازی بدون اتلاف داده، DEFLATE نام دارد که برای تصاویر PNG نیز استفاده می‌شود. این روش از ترکیب الگوریتم کدینگ هافمن و LZ77 ساخته شده است. از این روش در فشرده سازی gzip و ZIP نیز استفاده می‌شود. الگوریتم Lempel-Ziv-Welch یا LZW هم یکی دیگر از روش‌های فشرده سازی است بدون اتلاف داده است که روی داده‌ها یک آنالیز ساده و محدود انجام می‌دهد. از این روش در فرمت‌های TIFF و GIF استفاده می‌شود.

فشرده سازی با اتلاف داده

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

یک روش دیگر، تبدیل رمزگذاری (Transform encoding) است که برای تصاویر JPEG استفاده می‌شود. در این روش تصاویر با روش DCT یا تبدیل کسینوس گسسته به بلوک‌هایی تقسیم می‌شوند و در نهایت تصویری ایجاد می‌کنند که رنگ‌هایی کمتر از تصویر اولیه داشته باشد.

نمونه‌برداری کروما (Chroma subsampling) نام روش دیگری است که بر مبنای این اصل عمل می‌کند: «چشم انسان تغییرات در روشنایی را سخت‌تر از تغییر رنگ متوجه می‌شود.» نمونه‌برداری کروما اطلاعات روشنایی را نگه‌می‌دارد و برخی از اطلاعات رنگ را حذف می‌کند. از این روش در تصاویر JPEG و برخی الگوریتم‌های کاهش حجم ویدئو استفاده می‌شود.

انواع مختلف فایل‌ها

در این مقاله سه فرمت مشترک در طراحی وب یعنی PNG ،JPEG و GIF را معرفی می‌کنیم. غیر از این سه، تعداد زیادی فرمت دیگر هم وجود دارند که از روش‌های فشرده سازی استفاده می‌کنند، مثل: TIFF ،PCX ،TGA و غیره.

فرمت GIF

GIF یا فرمت تبادل گرافیکی (Graphics Interchange Format) در سال ۱۹۸۷ به‌وسیله CompuServe معرفی شد و یک فرمت تصویربرداری است. این فرمت تا ۸ بیت در هر پیکسل را پشتیبانی می‌کند، یعنی یک تصویر می‌تواند تا ۲۵۶ رنگ RGB مختلف داشته باشد. یکی از بزرگ‌ترین ویژگی‌های این فرمت توانایی ایجاد تصاویر متحرک است.

فرمت JPEG

JPEG یا Joint Photographic Experts Group فرمتی برای تصاویر است که از فشرده سازی با اتلاف داده استفاده می‌کند. یکی از بزرگ‌ترین مزیت‌های JPEG این است که به طراح اجازه می‌دهد مقدار فشرده سازی را به میزان لازم تنظیم کند. این کار نتیجه بهتری درباره کیفیت و اندازه مناسب به دست می‌دهد. چون JPEG از فشرده سازی با اتلاف داده استفاده می‌کند، تصاویری که با این فرمت ذخیره می‌شوند مصنوعی به نظر می‌رسند و می‌توان هاله نور عجیبی در قسمت‌های خاصی از آن‌ها دید. همچنین در بسیاری از قسمت‌های یک تصویر می‌توان کنتراست شدیدی بین رنگ‌ها مشاهده کرد.

فرمت PNG

PNG یا Portable Network Graphics یک فرمت تصویر است که از فشرده سازی بدون اتلاف داده استفاده می‌کند و برای جایگزین شدن فرمت GIF ایجاد شده است. این فرمت برای مدت طولانی در اینترنت اکسپلورر پشتیبانی نمی‌شد که به همین دلیل فرمت‌های JPEG و GIF متداول‌تر شدند؛ اگرچه در حال حاضر PNG در همه مرورگرها پشتیبانی می‌شود. یکی از بزرگ‌ترین مزیت‌های PNG این است که از تنظیمات متفاوت شفافیت (transparency)، مانند شفافیت کانال آلفا (alpha channel transparency)، پشتیبانی می‌کند.

انتخاب یک فرمت فایل مناسب

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

برای تصاویر گرافیکی ساده مانند لوگوها یا ترسیم خطوط، فرمت GIF بهتر کار می‌کند زیرا GIF پالت رنگ محدودی دارد. اگر پیچیدگی بیشتر باشد بهتر است از فرمت دیگری استفاده شود.

برای تصاویر با گرادیان، فرمت GIF مناسب نیست. در این موارد فرمت JPEG هنگامی مفید است که تصویر کنتراست شدیدی نداشته باشد. برای تصاویری با کنتراست بالا یا تصاویر شفاف، فرمت PNG بهترین فرمت است. در اغلب موارد اندازه تصاویر PNG از JPEG بزرگ‌تر است. توجه کنید که فایل‌های PNG از روش بدون اتلاف داده استفاده می‌کنند و کیفیت تصویر اولیه حفظ می‌شود.

در زیر به طور خلاصه، فرمت مناسب برای انواع تصویر را مرور می‌کنیم:

فرمت GIF

اگر در تصویری، انیمیشن، رسم خط یا تصویر گرافیکی ساده نیاز باشد، GIF بهترین گزینه است اما برای تصاویر گرادیان این فرمت مناسب نیست.

فرمت JPEG

برای اغلب تصاویر دوربین که کنتراست بالا ندارند یا برای بازی‌ها و فیلم‌ها این فرمت مناسب است. فرمت JPEG برای تصاویر دارای کنتراست بالا یا جزئیات بالا مناسب نیست، به طور مثال برای دیاگرام یا اینفوگرافیک. همچنین برای تصاویر گرافیکی ساده (به دلیل حجم بالا) بهتر است از فرمت GIF استفاده شود.

فرمت PNG

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

فشرده سازی در پرینت تصاویر

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

به منظور پرینت تصاویر فرمت TIFF یا Tagged Image File Format اغلب بهترین گزینه است. در این حالت باید از فرمت‌هایی (مانند LZW) استفاده کرد که فشرده سازی بدون اتلاف داده به حساب می‌آیند.

منبع

فشرده سازی تصویر قسمت 1
فشرده سازی تصویر قسمت 2

اکتبر 12, 2019/0 دیدگاه /توسط daliri