نوشته های Farbod Shahinfar

کپی پیست در StackOverflow پولی شد؟! نه دروغ ماه اپریل!

Farbod Shahinfar — Thu, 01 Apr 2021 14:52:14 +0430

من خیلی طرفدار رسم دروغ ۱۳ و یا دروغ اول ماه اپریل (April's Fools Day) نیستم. اطلاعی ندارم که این رسم از کجا شروع شده است و هدف از آن چه بوده است. ولی از آنجا که امروز خودم برای مدتی درگیر آن بودم، گفتم که درباره آن بنویسم.مثل همیشه در هنگام کار برای مرور جزئیات و کلیات دستورات ترمینال و Bash Script در حال جستوجو بودم و با دیدن لینک صفحه StackOverflow با خیال آسوده، می‌دانستم که اطلاعات مورد نیاز اولیه در این صفحه در دسترس است. بعد از مطالعه چند صفحه و دنبال کردن چند لینک، طبق عادت، کلمات کلیدی را از روی صفحه سایت StackOverflow کپی کردم و در این هنگام متوجه یک پیام جدید، عجیب و غیر منتظره شدم (شکل زیر).متن پیام، عجیب، غیر منتظره و غیر منطقی بود. برای اطمینان چند تا متن دیگر را کپی کردن و شمارنده کم شد. من میدانستم که هیچ راهی وجود ندارد که سایت StackOverflow بخواهد به راحتی جلوی کپی و پیست کردن مطالب را بگیرد. نمی‌خواهم وارد یک بحث فنی شوم ولی وقتی مرورگر شما صفحات وب را به صورت HTML دریافت می‌کند تمام اطلاعات لازم در آن قرار دارد. پس حتی اگر سعی کند با استفاده از جاوا اسکریپت جلوی کلید‌های ترکیبی و راست کلیک را بگیرد، باز هم نمی‌تواند متن اطلاعات را از دسترس دور نگهدارد (شاید اگر تمام صفحات را از HTML به عکس رندر کند و عکس را ارسال کند بشود ولی...). همچنین اگر با جاوا اسکریپت جلوی کپی پیست را بگیرد، آن وقت شخصی (شاید خودم، با احتمال خیلی پایین) پیدا می‌شود که کدی بنویسد که امکان کلیدهای ترکیبی و راست کلیک را دوباره فعال کند. برای این کار کافی است که کد جاوا اسکریپت جدید را در کنسول کپی پیست کنید و اجرا کنید. همچنین با غیر فعال کردن جاوا اسکریپت احتمالا دیگر در وهله اول امکان غیر فعال کردن وجود نخواهد داشت. به هر حال با این تفاسیر که به سرعت از ذهن من عبور کرد تقریبا مطمئن بودم که این از سمت StackOverflow نخواهد بود.پس اگر این پیام از سمت سایت اصلی نیست، از طرف چه کسی است؟ بوی خراب کاری می‌آمد. پروتکل صفحه https بود و آدرس درست بود. پس phishing نیست. من تعدادی افزونه اضافی روی مرورگرم دارم. به آن‌ها اعتماد نسبی دارم ولی هیچ وقت نمی‌توان مطمئن بود. من باید مطمئن می‌شدم که چه کدی در هنگام کلیک بر روی گزینه Learn More اجرا می‌شود. با استفاده از ابزار debug در مرورگر به کد زیر رسیدم.document.querySelector(".js-unlimited-modal-open-button").addEventListener("click", function() { return m() })در این کد تابع m در هنگام کیک بر روی دکمه اجرا می‌شود. این تابع به صورت زیر پیاده سازی شده است.function m() { var e, t, n, r, o; h(!1), document.querySelector(".js-modal-unlimited") .setAttribute("aria-hidden", "false"), y("aprilfools.notice_click", { "copy_count": c(), "variant": l() }); var i = new URL.toString()).searchParams; y("aprilfools.modal_display", { "utm_source": (e = i.get("utm_source"), null !== e && void 0 !== e ? e : ""), "utm_medium": (t = i.get("utm_medium"), null !== t && void 0 !== t ? t : ""), "utm_campaign": (n = i.get("utm_campaign"), null !== n && void 0 !== n ? n : ""), "utm_content": (r = i.get("utm_content"), null !== r && void 0 !== r ? r : ""), "utm_term": (o = i.get("utm_term"), null !== o && void 0 !== o ? o : "") }) } با دیدن این کد تازه متوجه موضوع شدم، امروز اول اپریل است و من قربانی روز اول اپریل. این کد اطلاعات صفحه‌ای که در حال مطالعه بودم و یکسری موارد که بشود کاربران را در وب‌سایت‌ها دنبال کرد جمع می‌کند و یک درخواست می‌فرستد. تقریبا مطمئن بودم که این کد نمی‌تواند کار خاصی را به تنهایی بکند مگر اینکه نتیجه فراخوانی تابع y موردی داشته باشد. با مطالعه سریع بقیه قسمت‌های کد تقریبا مطمئن بودم که قضیه جدی نیست. در هنگام کلیک کردن روی دکمه، صفحه فروش کلید مخصوص StackOverflow با اسم The Key که امکان Ctrl-C و Ctrl-V را به شما می‌دهد نشان داده می‌شود.در آخر می‌خواهم از StackOverflow و Wikipedia و دیگر سرویس‌هایی که اطلاعات با ارزش را به سادگی در دسترس عموم قرار می‌دهند تشکر و قدردانی کنم. از تمام کسانی که محتوای آن‌ها را ایجاد می‌کنند. کسانی که سوال می‌پرسند و کسانی که جواب می‌دهند. کسانی که مدیریت می‌کنند و کسانی که ویرایش می‌کنند. این حرکت دسته جمعی باعث رسیدن به نقطه‌ای است که نبودن آن‌ها واقعا احساس خواهد شد. https://stackoverflow.com/ اگر شما هم تجربه مشابه در روز اول اپریل با بقیه سرویس‌ها داشتید و خوشحال می‌شوم آن‌ها را در وقت فراغت بخوانم.

معرفی ابزار لینوکسی برای مدیران سیستم، mmwatch

Farbod Shahinfar — Sun, 14 Mar 2021 17:52:02 +0330

در سال ۲۰۱۷ در بلاگ cloudflare پستی با نام Three Little Tools: mmsum, mmwatch, mmhistogram منتشر شد. در این پست به سه ابزار ساده اشاره شده است که در کارهای اجرایی تیم مقابله با DDoS این شرکت استفاده می‌شود. در این پست به بررسی پیاده سازی mmwatch پرداخته می‌شود.شاید بهترین راه برای معرفی این ابزار از طریق نمایش عملکرد آن باشد.استفاده از mmwatch برای بدست آوردن نرخ تغییرات حجم فایلهمانطور که در تصویر دیده می‌شود، این ابزار دستور ls -lh را هر دو ثانیه یک بار اجرا می‌کند و در صورت تغییر در متغییرهای عددی، نرخ تغییرات را گزارش می‌کند. در این تصویر از آنجا که یک فایل در حال دانلود است حجم فایل تغییر می‌کند و نرخ تغییرات حجم به صورت highlight شده نشان داده می‌شود. mmwatch امکان بدست آوردن نرخ یک پارامتر را از روی بررسی تفاوت خروجی یک دستور فراهم می‌کند.برای استفاده از این ابزار می‌توانید کد آن را در این آدرس مشاهده کنید. برای راحتی کار می‌توانید مراحل زیر را دنبال کنید.cd /usr/bin sudo wget https://raw.githubusercontent.com/cloudflare/cloudflare-blog/master/2017-06-29-ssdp/mmwatch sudo chmod a+x mmwatchاین مراحل فایل mmwatch را از آدرس گفته شده دانلود می‌کند و در دایرکتوری /usr/bin قرار می‌دهد. سپس به آن دسترسی اجرایی اضاف می‌کند. با طی کردن این مراحل می‌توانید از دستور mmwatch استفاده کنید.برای تست کردن می‌توانید مانند تصویر بالا عمل کنید.کد این برنامه با زبان پایتون نوشته شده است. اگر برایتان سوال شده که این ابزار چطور پیاده شده است پیشنهاد می‌کنم که این بلاگ پست را مطالعه کنید. https://blog.fyro.ir/2021/03/14/mmwatch/

چطور دو تا ماشین لینوکسی را با کابل LAN مستقیم به یک دیگر وصل کنیم؟

Farbod Shahinfar — Fri, 26 Feb 2021 23:01:54 +0330

احتمالا تا الان به دفعات پیش آمده است که با استفاده از مدم خانگی و یا یک سویچ چندین کامپیوتر را به یک دیگر وصل کرده باشید. در این شرایط معمولا ماشین‌ها خودشان شبکه را شناسایی می‌کنند و به راحتی می‌توانید با دستور ping از اتصال میان آن‌ها اطمینان حاصل کنید. ولی اگر دو تا ماشین را مستقیم با کابل LAN به هم وصل کنید به احتمال زیاد متوجه می‌شوید که ماشین‌ها دارای آدرس IP مشخص نیستند و همچنین امکان Ping کردن ندارید. در این پست کوتاه، دستورات لینوکسی برای تنظیم دستی آدرس IP بر روی کارت‌های شبکه گفته می‌شود. برای اجرای این دستورات از بسته iproute2 که در اکثر سیستم‌های لینوکسی امروز موجود است استفاده می‌شود.در ابتدا لیست واسط‌های ارتباطی با شبکه را بدست می‌آوریم برای این منظور دستور زیر را اجرا می‌کنیم.ip addr showخروجی به شکل زیر خواهد بود.1: lo: ... 2: enp3s0: ... 3: wlp2s0: ...لینک‌هایی که با enp یا eth شروع می‌شوند مربوط به شبکه ethernet هستند که ما با کابل LAN می‌خواهیم آن‌ها را به یک دیگر وصل کنیم. لینک‌هایی که با wlp شروع می‌شوند ارتباط wireless هستند. حال برای اینکه دو دستگاه بتوانند با یک دیگر صحبت کنند کافی است که دو ماشین را با کابل LAN به یک دیگر متصل کنیم و به هر کدام یک آدرس IP بدهیم. برای تعیین آدرس IP بر روی یک درگاه از دستور زیر می‌توانید استفاده کنید.sudo ip addr add 10.0.0.10/24 dev enp3s0توجه کنید که enp3s0 اسم درگاه است که از مرحله قبل بدست آمد. آدرس IP انتخاب شده برای این درگاه به صورت 10.0.0.10/24 انتخاب شده است. برای اینکه ماشین دوم بتواند این آدرس را پیدا کند توجه کنید برای درگاه ماشین دوم، آدرسی در محدود مرتبط با ماشین اول انتخاب کنید. مثلا اگر آدرس ماشین اول را به صورت گفته شده تعیین کرده‌اید می توانید از آدرس 10.0.0.20/24 برای ماشین دوم استفاده کنید.پس از پایان این مراحل از هر کدام از ماشین‌ها می‌توانید ماشین دیگر را ping کنید.لینک مرجعمنبع عکس

کامیت‌های مخزن گیت خود را امضا کنید.

Farbod Shahinfar — Tue, 17 Dec 2019 00:44:18 +0330

مقدمهگیت یک برنامه مدیریت نسخه‌های پروژه است که اعضا تیم با ثبت کردن تغییرات خود در یک مخزن تاریخچه‌ای از نسخه‌های متفاوت پروژه را ثبت می‌کنند. در این نوشتار فرض شده است که خواننده با گیت و چگونگی کار با آن آشنایی کافی را دارد و فقط به این مطلب اشاره می‌شود که چگونه تغییرات اعمالی خود را با امضای دیجیتال خود تایید کنیم تا تمام اعضای تیم مطمئن شوند که تغییرات اعمال شده واقعا از سمت ما اعمال شده است.چرا کامیت‌های خود را امضا کنیماگر توجه کرده باشید در هنگام مشاهده کامیت‌های صورت گرفته در یک مخزن نام و ایمیل شخصی که آن کامیت‌ها را ثبت کرده است هم نمایش داده می‌شود. این نام و آدرس ایمیل با توجه به تنظیماتی که در برنامه گیت انجام داده‌اید ذخیره می‌شود و هر شخصی می‌تواند با هر نام و آدرس ایمیل اقدام به ذخیره یک کامیت کند. این موضوع نشان می‌دهد که نمی‌توان به اسمی که در تاریخچه گیت نمایش داده می‌شود اعتماد کرد. برای اینکه مطمئن شویم هر کامیت را چه شخصی انجام داده است، این امکان در برنامه گیت فراهم شده است که تغییرات اعمالی توسط هر شخص با امضای دیجیتال آن شخص علامت گذاری شود. در این صورت مطمئن هستیم که تغییرات حتما از سمت شخص نام برده شده، اعمال شده است.اگر از گیت‌هاب استفاده می‌کنید در صورت امضا کردن کامیت‌ها و تعریف کردن امضای خود به گیت‌هاب، در تاریخچه کامیت‌ها کنار هر کامیت عبارت verified نوشته می‌شود.عبارت verified در کنار شناسه کامیت‌ها در گیت‌هابچگونه گیت را تنظیم کنیمابتدا باید یک امضا الکترونیک برای خود ایجاد کنیم. برای این کار از برنامه gpg استفاده می‌کنیم. این برنامه به احتمال زیاد بر روی نسخه لینوکس‌تان وجود دارد. در صورت نیاز آن را نصب کنید و با دستور زیر یک کلید ایجاد کنید.gpg --gen-keyبا اجرای دستور بالا چند سوال از جمله نام شما را می‌پرسد و از شما می‌خواهد تا برای امضای خود یک کلمه عبور انتخاب کنید.پس از ساخت کلید با اجرا دستور زیر اطلاعات کلید ساخته شده را مشاهده کنید.gpg --list-keys --keyid-format LONGخروجی قالبی مشابه به متن زیر خواهد داشت.--------------------------------- pub 2048R/0A46826A 2014-06-04 uid Scott Chacon (Git signing key) sub 2048R/874529A9 2014-06-04 در خط اول، بخش بعد از « / » نشان دهنده id کلید شما است. از این id برای تنظیم کلیدی که در امضا کردن کامیت‌ها بکار می‌رود، استفاده می‌شود.در ادامه برنامه گیت را باید تنظیم کنیم. با اجرای دستور زیر کلید مورد نظر خود برای امضا کردن را، به برنامه گیت معرفی می‌کنیم.git config --global user.signingkey در بخش باید مقداری که از بخش قبل بدست آوردید را قرار دهید. (در این مثال 0A46826A عبارت نشان دهنده key_id است)پس از این تغییرات با استفاده از دستور زیر می‌توانیم کامیت‌های خود را امضا کنیم. (-S برای امضا کردن آمده است)git commit -S -a -m "Test a signed commit"برای این که در هر کامیت عبارت -S را تکرار نکنیم می‌توانیم تنظیم زیر را انجام دهیم.git config --global commit.gpgsign trueتنظیم کردن گیت‌هاب برای نمایش عبارت verifiedگیت‌هاب کامیت‌های امضا شده را با عبارت verified نشان می‌دهد. فقط کافی است امضا خود را به گیت‌هاب معرفی کنید. برای این منظور دستور زیر را اجرا کنید. (key_id از بخش‌های قبلی بدست آمده است.)gpg --armor --export خروجی این دستور با عبارت -----BEGIN PGP PUBLIC KEY BLOCK----- شروع می‌شود و با عبارت -----END PGP PUBLIC KEY BLOCK----- پایان می‌یابد. (محتوای کلید عمومی شما را نشان می‌دهد که به دیگران این امکان را می‌دهد که امضای شما را شناسایی کنند و متوجه شوند که این امضا حقیقتا به شما تعلق دارد.)متن خروجی دستور بالا را (به همراه دو عبارت ‌که نشان دهنده شروع و پایان است) کپی کنید و در بخش تنظیمات حساب کاربری خود در سایت گیت‌هاب به بخش SSH and GPG keys مراجعه کنید و دکمه new GPG key را انتخاب کنید. متنی را که کپی کرده‌اید در بخش مورد نظر وارد کنید و دکمه اضافه کردن را فشار دهید. تنظیمات مربوط به گیت‌هاب در همین جا به پایان می‌رسد.منابعمطالب این نوشتار از مطالعه کردن سایت‌های زیر بدست آمده است. درصورت نیاز به مطالعه بیشتر به آن‌ها مراجعه کنید و یا سوال خود را در بخش نظرات مطرح کنید تا با هم آن را بررسی کنیم.https://git-scm.com/book/en/v2/Git-Tools-Signing-Your-Workhttps://help.github.com/en/github/authenticating-to-github/generating-a-new-gpg-keyhttps://help.github.com/en/github/authenticating-to-github/signing-commitshttps://gist.github.com/mort3za/ad545d47dd2b54970c102fe39912f305

در کرنل لینوکس LinkedList چگونه پیاده شده است؟

Farbod Shahinfar — Tue, 20 Aug 2019 11:48:12 +0430

عکس از لینکمقدمهدر این نوشته به چگونگی پیاده سازی یک داده ساختار معروف به نام LinkedList در کرنل لینکوس (Linux) می‌پردازیم. مخاطبان احتمالی این مطلب کسانی هستند که به برنامه نویسی و (چگونگی) توسعه کرنل لینکوس علاقه دارند. (جستوجو کنید kernel hacker)در ابتدای این مطلب به معرفی داده‌ساختار (Data Structure) LinkedList پرداخته می‌شود. سپس در ادامه پیاده سازی آن در کرنل لینوکس بررسی می‌گردد. (در فارسی LinkedList را لیست‌پیوندی ترجمه کرده‌اند.)+ نسخه کرنل استفاده شده 5.2 می‌باشد. (می‌توانید نسخه‌های متفاوت را از لینک دریافت کنید.)معرفی LinkedListیکی از داده‌ساختارهای ابتدایی که هر برنامه نویسی باید با آن آشنا باشد، LinkedList است. LinkedList برای ذخیره مجموعه‌ای از اطلاعات به صورت مرتب و با ترتیب خطی استفاده می‌شود و از این جهت به آرایه‌ها شبیه است. از طرفی، برخلاف آرایه، اندازه (تعداد عناصر) LinkedList می‌تواند در زمان اجرا تغییر کند و نیازی نیست که در هنگام استفاده از همان ابتدا یک بخش ثابت از حافظه را به این داده‌ساختار اختصاص داد.ساختار LinkedList به صورت زنجیره‌ای از عناصر است که هر عنصر آدرس عنصر بعدی خود را می‌داند. به این صورت می‌توان از هر عنصر آدرس خانه بعدی که اطلاعات مورد نظر ما در آن قرار دارد را پرسید و از یک عنصر به عنصر بعدی رسید (مانند شکل زیر). از آنجا که هر عنصر آدرس عنصر بعدی در حافظه را می‌داند، برخلاف آرایه‌ها، دیگر نیازی نیست تا آدرس حافظه اطلاعات ذخیره شده به صورت پیوسته و به دنبال هم باشد. (به عبارت دیگر عناصر موجود در یک LinkedList لزوما در خانه‌های مجاوری از حافظه قرار نمی‌گیرند.)این امکان که بتوان داده‌ها را در مکان‌ها متفاوتی از حافظه قرار داد و آن‌ها را به یک دیگر مرتبط ساخت باعث می‌شود بتوان فرآیند افزودن و حذف کردن اطلاعات از یک لیست را تسریع کرد. چرا که در آرایه ها برای اضافه کردن یک عنصر در میانه لیست نیاز است تمام عناصر بعدی یک خانه به جلو انتفال یابند و در هنگام حذف کردن تمام عناصر قبلی باید یک خانه به عقب انتقال یابند تا فضای خالی پرشود.شمایی از ساختار LinkList (از سایت ویکیپیدیا)به دلیل ساختار LinkedList و پیوسته نبودن آدرس عناصر آن در حافظه، برخلاف آرایه، امکان Random Access به عناصر وجود ندارد.اگر هر عنصر LinkedList علاوه بر عنصر بعدی، آدرس عنصر قبلی خود را هم بشناسد به آن Doubly LinkedList می‌گویند.پیاده سازی Doubly LinkedList در کرنل لینوکسساختار (struct) list_head نشان دهنده یک عضو در زنجیره داده‌ساختار Doubly LinkedList تعریف شده در کرنل لینوکس است. تعریف list_head در فایل (include/linux/types.h) types.h به صورت زیر پیدا می‌شود.struct list_head { struct list_head *next, *prev; };در این ساختار مشاهده می‌شود که دو اشاره‌گر وجود دارد که یکی به عنصر بعدی و دیگری به عنصر قبلی اشاره می‌کند.هر عضو از نوع list_head می‌تواند به عنوان شروع یک لیست تفسیر شود. پس اشاره‌گر به ابتدای لیست با اشاره‌گر به اعضای درون لیست تفاوتی ندارد.نکته قابل توجه در مورد این نحوه تعریف Doubly LinkedList آن است که هیچ حافظه‌ای برای داده‌ای که قرار است نگهداری شود در نظر گرفته نشده است. و در نگاه اول اینگونه تعریف داده‌ساختار بدون کاربرد بنظر می‌رسد.در واقع توسعه دهندگان کرنل با زیرکی خاصی این داده‌ساختار را بگونه‌ای طراحی کرده‌اند که بتوان برای تعریف لیستی از انواع مختلف داده استفاده کرد.به عنوان مثالی از استفاده از list_head لیست formats را بررسی می‌کنیم. در این مثال هدف ما تمرکز بر ایجاد لیستی از انواع داده دلخواه است. جدا از چرایی وجود لیست formats و نقشی که در کرنل بازی می‌کند، در این لیست مجموعه‌ای از ساختار linux_binfmt نگهداری می‌شود. پیاده سازی این ساختار را در ادامه مشاهده می‌کنید./* * This structure defines the functions that are used to load the binary formats that * linux accepts. */ struct linux_binfmt { struct list_head lh; struct module *module; int (*load_binary)(struct linux_binprm *); int (*load_shlib)(struct file *); int (*core_dump)(struct coredump_params *cprm); unsigned long min_coredump; /* minimal dump size */ } __randomize_layout;اولین مشخصه این ساختار، فیلد lh، از نوع list_head است و طبق تعریفی که در بالا آورده شده است؛ فیلد lh دارای اشاره‌گر به عنصر بعدی و قبلی است. همان طور که می‌دانید نوع عنصری که lh به آن اشاره می‌کند از نوع list_head هست و نه از نوع linux_binfmt. سوال مهم این است که با این شرایط چطور می‌توان به عنصر بعدی linux_binfmt دسترسی داشت؟ شکل زیر به طور نمادین نحوه قرار گیری linux_binfmt در حافظه را نمایش می‌دهد. همان طور که می‌بینید در هر عنصر از ساختار linux_binfmt فیلد lh مکان قرار گیری lh عنصر بعدی را در حافظه می‌شناسد (خطوط قرمز). حال اگر بدانیم فیلد lh چند واحد از شروع عنصر در حافظه فاصله دارد (offset)، می‌توانیم آدرس lh عنصر بعدی را منهای offset کنیم تا ابتدای ساختار linux_binfmt را بدست آوریم.پس به طور خلاصه با دنبال کردن list_head آدرس یک فیلد از ساختاری که اطلاعات مورد نظر را دارد را پیدا می‌شود و سپس با دانستن offset آن فیلد به ابتدای ساختار دسترسی خواهیم داشت.قرار گیری ساختار linux_binfmt در حافظهپیاده سازی این فرآیند در کرنل توسط یک macro به نام list_entry صورت می‌گیرد. در ادامه پیاده سازی این macro بررسی می‌شود./** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member)توضیح پارامتر‌هایی که به list_entry (و سپس به container_of) داده می‌شود به این صورت است. ptr اشاره‌گر به یک عنصر list_head است (در این مثال عنصر بعدی که lh به آن اشاره می‌کند). type نوع ساختاری که باید دریافت شود را مشخص می‌کند (در این مثال struct linux_binfmt). و member نام فیلدی درون ساختار گفته شده است که لیست مورد نظر ما را تشکیل می‌دهد (در این مثال lh).همان طور که مشاهده می‌شود list_entry به صورت مستقیم container_of را فراخوانی ‌میکند. پیاده سازی container_of به صورت زیر است. (این پیاده سازی در فایل include/linux/kernel.h قرار دارد.)/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \ !__same_type(*(ptr), void), \ "pointer type mismatch in container_of()"); \ ((type *)(__mptr - offsetof(type, member))); })این macro عجیب دقیقا همان کاری را می‌کند که دربالا گفته شد. یک اشاره‌گر را به عنوان ورودی ‌می‌گیرد (همان آدرس lh عنصر بعدی). بعد در خط آخر یک اشاره‌گر از نوع معین شده (type) بازگشت داده می‌شود که آدرس آن از تفریق آدرس گفته شده (ptr) و offset عضو داده شده (member) بدست می‌آید.فاصله فیلد از ابتدای ساختار تعریف شده توسط offsetof محاسبه می‌شود که کد آن در ادامه آمده است.#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)این macro بیان می‌کند که اگر ساختار در خانه صفر حافظه باشد آنگاه عضو گفته شده چه آدرسی خواهد داشت. این همان offset است که با تفریق از آدرس اشاره‌گر ما را به ابتدای ساختار می‌رساند.کد زیر یک مثال از استفاده از list_entry است. (کد زیر از کرنل لینوکس نیست.)... struct linux_binfmt next_element = list_entry(features.lh.next, struct linux_binfmt, lh); ...در ادامه دیگر توابع و macro های پیاده سازی شده برای list_head به طور خلاصه معرفی می‌شود.در کرنل تعدادی macro برای کار با list_head وجود دارد. برای تعریف یک لیست از LIST_HEAD استفاده می‌شود که به صورت زیر تعریف شده است.#define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)این macro یک اسم می‌گیرد و یک لیست با نام گفته شده تشکیل می‌دهد. در تعریف LIST_HEAD از یک macro دیگر با نام LIST_HEAD_INIT استفاده شده است که مقدار اولیه اشاره‌گر‌ بعدی و قبلی را برابر عنصر جدید ایجاد شده قرار می‌دهد. (انتها یک لیست وقتی است که عنصر بعدی همان عنصر ابتدایی است.)برای ایجاد تغییر در لیست مجموعه‌ای از توابع مانند list_add، list_del، list_add_tail و ... موجود است. این توابع در فایل list.h (include/linux/list.h) تعریف گشته‌اند و نام آن‌ها به وضوح کاری را که انجام می‌دهند را مشخص می‌کند.جمع بندیدر این نوشته به طور مختصر داده‌ساختار LinkedList معرفی شد و در ادامه بخش‌هایی از پیاده سازی کرنل لینوکس که مربوط به این داده‌ساختار بود بررسی گشت. (همچنین آدرس پیاده سازی آن‌ها در این نوشته موجود است. برای کسانی که علاقه به مطالعه بیشتر و دنبال کردن آن دارند).امیدوارم این نوشته به بخشی از سوالات شما درباره چگونگی کارکرد کرنل لینوکس پاسخ داده باشد.

الگوریتم ژنتیک و مسئله هشت وزیر

Farbod Shahinfar — Tue, 04 Jun 2019 16:48:14 +0430

چکیدهدر ابتدا با الگوریتم ژنتیک معرفی می‌شود و مراحل لازم برای حل یک مسئله به این روش را مطرح می‌گردد. سپس تلاش می‌کنیم مسئله هشت وزیر را با استفاده از این روش حل کنیم. در انتها پیاده سازی این راه حل مطرح شده برای مسئله هشت وزیر با زبان سی پلاس پلاس را بررسی می‌کنیم.مقدماتالگوریتم ژنتیک زیر مجموعه‌ای از الگوریتم‌های تکاملی است. این الگوریتم از سیستم بیولوژی بدن الهام گرفته شده است. در این الگوریتم نیاز است که بتوانیم هر پاسخ ممکن به مسئله را در یک ساختار مناسب نمایش دهیم (به این نمایش chromosome representation می‌گویند). در ادامه، یک تابع نیاز است تا هر نمونه جواب (که در ساختار مناسب نمایش داده شده است) را به مقدار عددی نگاشت کند. این تابع باید میزان مناسب بودن یک پاسخ برای مسئله را نشان دهد. این تابع را اصطلاحا fitness function می‌نامند. پس از مشخص شدن ساختار نمایش یک پاسخ در مساله و تابع ارزیابی آن، یک نسل اولیه از پاسخ‌ها تولید می‌شود و با اعمال فرآیند‌ها ژنتیک از نسل اولیه نسل‌های بعدی به وجود می‌آید و این روند تکرار می‌گردد تا پاسخ مناسب پیدا گردد. این الگوریتم برای یافتن پاسخ مسائلی مناسب است که فضای جستوجوی آن‌ها بسیار گسترده است و راه‌های عددی شناخته شده نمی‌توانند ما را در رسیدن به جواب کمک کند. همچنین در شرایطی که شناخت ریاضی از مسئله نداریم ولی می‌توانیم میزان مناسب بودن یک پاسخ را اندازگیری کنیم، استفاده از این روش‌ها می‌تواند در پیدا کردن پاسخ مسئله کمک کند.پاسخ‌های بدست آمده از الگوریتم ژنتیک بهترین جواب ممکن نیست. در واقع هیچ تضمینی برای یافتن پاسخ بهینه با استفاده از این الگوریتم وجود ندارد. ولی با استفاده از این الگوریتم می‌توان به جواب‌هایی رسید که تا حد کافی مناسب باشند. در نتیجه این مطلب، استفاده از این روش در مسائلی که نیاز به پیدا کردن پاسخ بهینه مطلق است مناسب نیست ولی برای پیدا کردن یک پاسخ نزدیک به جواب بهینه می‌تواند استفاده گردد.مراحل این الگوریتمتولید نسل اولیه (Initialization)انتخاب (Selection)عملگر‌های ژنتیکی (Genetic Operations)تولید نسل اولیهدر این فاز تعدادی پاسخ برای مسئله به صورت تصادفی ایجاد می‌شود (معمولا بین ۵۰ تا ۱۰۰ پاسخ).انتخاباز نسل قبلی تعدادی از پاسخ‌ها انتخاب می‌شوند تا مولد پاسخ‌های جدید باشند. برای این انتخاب شیوه‌های متفاوتی پیشنهاد شده است. این انتخاب می‌تواند به صورت کاملا تصادفی باشد. راه دیگر مورد استفاده می‌تواند این باشد که تعدادی از بهترین جواب‌ها را حتما در انتخاب خود داشته باشیم و دیگر پاسخ‌ها به صورت تصادفی انتخاب شوند. یک پیشنهاد دیگر آن است که به صورت تصادفی از میان جمعیت قبلی انتخاب صورت گیرد با این تفاوت که احتمال انتخاب آن پاسخ‌هایی که برای مسئله مناسب‌تر ارزیابی شده‌اند بیشتر از دیگر پاسخ‌ها باشد (به این روش چرخ رولت هم می‌گویند).عملگر‌های ژنتیکیپس از انتخاب والد‌های نسل بعد با استفاده از عملگر‌های ژنتیک نسل بعدی را ایجاد می‌کنیم. یک نکته قابل مطرح آن است که تعداد پاسخ‌های هر نسل را برابر در نظر می‌گیرند و اندازه نسل را معمولا تغییر نمی‌دهند.دو عملگر معروف برای ایجاد نسل جدید عبارت‌اند از:برش (Crossover)جهش (Mutation)عمل برش اینگونه است که از ترکیب اطلاعات دو والد یک پاسخ جدید به وجود می‌آید. اگر یک نمایش به صورت رشته بیتی از پاسخ را درنظر بگیریم، شکل زیر می‌تواند این فرآیند را نمایش دهد. (تصویر از toturialspoint)نحوه تعریف این عملگر بسته به تعریف مسئله و چگونگی نمایش پاسخ می‌تواند به صورت‌های متفاوت تعریف گردد. برای مثال در شکل بالا، برای برش یک نقطه انتخاب شده است. این تعداد می‌تواند بیشتر از یک باشد و یا اینکه برای هر بیت به صورت جداگانه تصمیم گیری شود.عمل جهش اینگونه است که مقادیر پاسخ به صورت تصادفی با یک احتمال ( معمولا این احتمال کم است.) تغییر می‌کند و مقادیر دیگری اختیار می‌کنند. برای مثال در یک نمایش دنباله بیتی می‌توان عمل جهش را به تغییر تصادفی هر کدام از بیت‌ها از یک به صفر و یا برعکس تعریف کرد.شرایط پایانپس از انجام عملیات بالا یک نسل جدید از پاسخ‌ها بدست می‌آید. سوال این است که در چه وقت ادامه فرآیند باید متوقف شود. برای شرط پایان پاسخ دقیقی مطرح نیست. یک پیشنهاد آن است که تعداد نسل ثابتی را بررسی گردد. برای مثال فرآیند بالا را برای ۱۰۰۰ نسل تکرار شود و بهترین پاسخ از میان آن‌ها انتخاب گردد. پیشنهاد دیگر می‌تواند آن باشد که تا رسیدن به مقدار ارزیابی (fitness) مورد نظر این فرآیند را تکرار شود.پیاده سازی مسئله هشت وزیر با استفاده از الگوریتم ژنتیککد کامل استفاده شده برای این سوال در این لینک قرار دارد.تعریف مسئلهدر یک صفحه شطرنج تعداد هشت وزیر را به نحوی قرار دهید تا یک دیگر را تحدید نکنند. این مسئله در دسته مسائل CSP (Constraint Satisfaction Problems) قرار می‌گیرد و با روش‌های متفاوتی می‌توان آن را حل کرد. در ادامه برای نمایش چگونگی استفاده از الگوریتم‌ ژنتیک به حل این مسئله می‌پردازیم.تعریف ساختار مناسب برای پاسخ این مسئلهراه‌های متفاوتی برای نمایش پاسخ‌های این مسئله وجود دارد. در این نوشتار مسئله با استفاده از یک بردار به طول ۸ نمایش داده شده است. مقدار هر کدام از عناصر این بردار می‌تواند بین ۰ تا ۷ باشد. تفسیر این ساختار به این نحوه است که هر درایه از بردار، محل قرار گیری وزیر در یک ستون را نمایش می‌دهد. برای مثال درایه سوم، محل قرار گیری وزیر در ستون سوم را مشخص می‌کند. این شیوه نمایش به صورت خودکار امکان بررسی جواب‌هایی که دو وزیر در یک ستون قرار می‌گیرد را حذف می‌کند.تعریف تابع ارزیابی برای ارزیابی هر جواب در ابتدا، تعداد تحدید دو به دو هر وزیر مشخص می‌شود. این تعداد حد اکثر ۲۸ مورد است چرا که C(8, 2) = 28 (انتخاب دو از هشت برابر بیست هشت است). سپس این تعداد را بر مقدار حداکثر که همان ۲۸ است تقسیم می‌گردد. هر چه این مقدار کمتر باشد پاسخ مناسب‌تری برای مسئله است. و پاسخ نهایی آن است که هیچ وزیری تحدید نشود. برای راحتی، این مقدار از یک کم می‌شود تا حاصل عددی باشد که هرچه بیشتر باشد بهتر است.float fitness_function(Entity &e) { int threats = 0; // total possible threats = C(2, 8) = 28 // this value is for 8 queens const int total_posible_threats = 28; for (int col = 0; col < Entity::COUNT_COLUMN; col++) { int col_val = e.get_column(col); for (int ptr = col + 1; ptr < Entity::COUNT_COLUMN; ptr++) { int ptr_val = e.get_column(ptr); if (col_val == ptr_val) { // in same row threats++; } else if (ptr - col == ptr_val - col_val) { // diagonal `/` threats++; } else if (ptr - col == col_val - ptr_val) { // diagonal `\` threats++; } } } return 1 - (threats / (float)total_posible_threats); }تولید نسل اولنسل اول به صورت کاملا تصادفی ایجاد می‌شود. برای ایجاد هر پاسخ یک عدد تصادفی بین ۰ تا ۷ در هر درایه بردار قرار می‌گیرد.default_random_engine Entity::generator; uniform_int_distribution Entity::distribution(0, COUNT_ROW-1); /* * This function generates a new Entity object */ Entity* Entity::generate_random_entity() { Entity *entity = new Entity(); for (int col = 0; col < COUNT_COLUMN; col++) { int row = distribution(generator); entity->set_column_row(col, row); } return entity; } Entity* generate_random_population(int size) { Entity* population =new Entity[size]; Entity* e; for (int i = 0; i < size; i++) { e = Entity::generate_random_entity(); population[i] = *e; } return population; }انتخاببرای انتخاب از میان یک نسل از روش چرخ رولت استفاده شده است. در این روش احتمال انتخاب هر پاسخ متناسب با مقدار ارزیابی آن پاسخ است. (برای مطالعه بیشتر به این لینک مراجعه کنید.)Entity* select_from_population(Entity* population, const int size) { float comulative_f[size]; float normal_f; float comulative = 0; float total_f = 0; // calculate sum of f value for normalization for (int i = 0; i < size; i++) total_f += fittness_function(population[i]); // generate the commulative value for (int i = 0; i < size; i++) { normal_f = fittness_function(population[i]) / total_f; comulative += normal_f; comulative_f[i] = comulative; } // select parents randomly with // respect to fittness Entity* selected = new Entity[size]; double max_rnd = (double)(RAND_MAX) + 1; for (int i = 0; i < size; i++) { double rnd = rand() / max_rnd; int ptr = 0; while (ptr < size - 1) { if (comulative_f[ptr] >= rnd) break; ptr++; } selected[i] = population[ptr]; } return selected; }اعمال عملگر‌های ژنتیکدر این بخش برش بر روی پاسخ‌های انتخاب شده اعمال می‌شود. این برش به این صورت تعریف گشته است که در ابتدا پاسخ‌ها به دسته‌های دو تایی تقسیم می‌گردند و سپس یک نقطه از پاسخ‌ها به صورت تصادفی انتخاب می‌گردد و اطلاعات دو پاسخ تا قبل از آن نقطه و بعد از آن جابه‌جا می‌گردد.Entity* cross_over(Entity* population, const int size) { if (size % 2 != 0) throw invalid_argument("population size is not even number!"); Entity* result = new Entity[size / 2]; int pop_index = 0; for (int i = 0; i < size; i += 2) { Entity* xover = new Entity(); int xover_pnt = rand() % Entity::COUNT_COLUMN; for (int j = 0; j < Entity::COUNT_COLUMN; j++) { int val; if (j <= xover_pnt) { val = population[i].get_column(j); } else { val = population[i + 1].get_column(j); } xover->set_column_row(j, val); } result[pop_index++] = *xover; } return result; }شرط پایانچرخه ایجاد نسل جدید آنقدر تکرار می‌گردد تا یک پاسخ با مقدار ارزیابی شده یک پیدا شود.

شبکه عصبی Kohonen

Farbod Shahinfar — Sun, 26 May 2019 20:47:57 +0430

خلاصه مطلبدر این نوشتار به معرفی مقدمات و ساختار یک شبکه عصبی خود سازمان‌ده به نام شبکه عصبی Kohonen می‌پردازیم و در ادامه، پس از بیان مقدمات لازم برای آشنایی با مراحل یادگیری این شبکه و نحوه عملکرد آن، یک مثال از آن با استفاده از زبان برنامه نویسی پایتون پیاده شده است.مقدماتمدل شبکه عصبی Kohonen یک شبکه عصبی مصنوعی است برای ایجاد SOFM یاSelf Organizing Feature Map. یادگیری این شبکه به صورت بدون ناظر (unsupervised) صورت می‌گیرد. این شبکه برای دسته‌بند ورودی‌ها به صورت خودکار استفاده می‌شود. حاصل این شبکه معمولا یک نمایش گسسته از اطلاعات (map) است که معمولا ابعادی کوچک‌تر از ابعاد ورودی دارد. از کاربرد‌های این شبکه می‌توان به clustering، space approximation و data visualization نام برد.ساختار مدل kohonen. منبع عکسساختار شبکه‌های kohonen، علاوه بر تعداد نورون استفاده شده در شبکه، دارای پارامتر ابعاد نقشه هم می‌باشد (برای مثال شکل بالا یک نگاشت از یک فضای n بعدی به یک فضای دو بعدی است). در این مدل ورودی مدل به تمام نورون‌ها متصل است. هر کدام از این اتصالات دارای وزن می‌باشد. پس هر نوران در این شبکه دارای یک بردار وزن است که اندازه آن برابر با اندازه بردار ورودی است. در نتیجه‌ی فرآیند یادگیری مقدار این وزن‌ها تغییر پیدا می‌کند به طوری که خروجی به مقدار ورودی نزدیک‌تر گردد. پس از یادگیری، شبکه بدست آمده اطلاعات پراکندگی داده‌های استفاده شده در آموزش شبکه را مدل می‌کند (مانند شکل زیر).عکس از ویکیپیدیادر این مدل نورون‌های همسایه با یک دیگر در ارتباط هستند. همان طور که گفته شده این مدل برای تشکیل یک feature map بدون ناظر از ورودی استفاده می‌شود. در این شبکه تلاش می‌شود ورودی‌هایی که به یک دیگر نزدیکتر هستند در map بدست آمده در همسایگی هم قرار گیرند.فرآیند یادگیریفرآیند یادگیری این شبکه دارای مراحل زیر است:۱. مقدار دهی اولیه۲. رقابت۳. همکاری ۴. تطبیقمقداردهی اولیهدر این مرحله مقدار وزن‌های مربوط به هر نورون باید مقدار دهی شود. برای مقدار دهی این وزن‌ها روش‌های متفاوتی مطرح شده است. می‌توان آن‌ها را به صورت تصادفی مقدار دهی کرد. یا از مولفه‌های اصلی داده‌ها برای این کار استفاده کرد.رقابتدر هر iteration با معرفی یکی از اطلاعات موجود در دادگان آموزش به مدل، نورونی که کوتاه‌ترین فاصله را از آن ورودی دارد انتخاب می‌شود. به این نورون اصطلاحا BMU (Best Matching Unit) گفته می‌شود. این فاصله همان فاصله اقلیدسی میان بردار وزن نورون و اطلاعات ورودی است. در رابطه زیر x مقدار بردار ورودی است و w_i مقدار بردار وزن برای نورون iام است.همکاریدر این فرآیند یک تابع همسایگی تعریف می‌شود که قصد آن تعیین میزان تاثیر گذاری مرحله تطابق برروی همسایگان BMU است. به همین دلیل حاصل این تابع مقداری در بازه [0,1] است. هدف این تابع این است که باعث شود همسایگان یک نورون ویژگی‌های نزدیک به یک دیگر را مدل کنند.این تابع همسایگی باید بیشترین تاثیر را بر روی BMU داشته باشد و هر چه فاصله از این نورون بیشتر می‌شود میزان تاثیر گذاری باید کاهش یابد. در اینجا، بر خلاف حالتی که فاصله تا یک بردار ورودی محاسبه می‌شد، منظور از فاصله میان دو نورون فاصله آن‌ها بر روی نقشه است. این فاصله را می‌توان به صورت‌های متفاوتی تعریف کرد. مثلا در یک شبکه دوبعدی می‌توان فاصله قرار گیری نورون در شبکه (مختصات نورون در شبکه) را در نظر داشت.یکی از پارامتر‌های مهم این تابع شعاع همسایگی است. این شعاع باید مشخص کند که تا چه فاصله‌ای از BMU این تغییرات باید اعمال گردد (پارامتر ورودی تابع همسایگی فاصله از BMU است). یکی از توابعی که مناسب این هدف است تابع گوسی است. در تابع گوسی شعاع همسایگی را می‌توان معادل واریانس در نظر گرفت.یکی از نکاتی که در آموزش شبکه‌های kohonen مطرح می‌شود این است که شعاع همسایگی در ابتدای فرآیند بزرگ در نظر گرفته شود به صورتی که تمام نورون‌های دیگر را تحت تاثیر قرار دهد چرا که وزن‌های شبکه به مقدار نهایی خود نزدیک نیستند. سپس با گذشت هر epoch این شعاع کاهش یابد تا نورون‌های کمتری را تحت پوشش قرار دهد. تطبیقدر این مرحله وزن تمام نورون‌ها (با توجه به تابع همسایگی ) به نحوی تغییر می‌یابد تا شبکه داده‌ها را بهتر مدل کند. میزان تغییر وزن هر نورون از رابطه زیر پیروی می‌کند. فاصله بردار وزن نورون تا ورودی محاسبه می‌شود. سپس باتوجه به فاصله اش از ‌BMU مقدار این فاصله در میزان تاثیری که تابع همسایگی مشخص می‌کند ضرب می‌شود. در نهایت کل عبارت در یک ضریب یادگیری ضرب می‌شود. مقدار ضریب یادگیری بین صفر و یک است. (رابطه زیر از تئوری هب پیروی می‌کند.)استفاده از مدل آموزش دیدهپس از آموزش، از مدل بدست آمده می‌توان برای نمایش اطلاعات استفاده کرد که در این صورت با ترسیم مناسب نقشه بدست آمده می‌توان به این هدف رسید. همچنین می‌توان از آن برای دسته‌بندی اطلاعات جدید استفاده کرد به گونه‌ای که با ورودی دادن اطلاعات جدید نورونی که کمترین فاصله را دارد (همان BMU) نمایانگر دسته اطلاعات ورودی است.یک نمونه از این شبکهدر ادامه این مطلب یک شبکه عصبی kohonen را پیاده سازی می‌کنیم که رنگ‌های موجود در یک عکس را دسته بندی می‌کند.‌هدف این شبکه این است که مقدار RGB تک تک پیکسل‌های یک عکس را به عنوان داده آموزشی به این شبکه بدهیم و در نهایت یک نقشه از رنگ‌های استفاده شده در این عکس بدست بیاوریم. (به عکس‌های زیر توجه کنید.)عکس ورودعکس خروجیبرای پیاده سازی این شبکه از زبان برنامه نویسی python استفاده کرده‌ایم. و فقط از ماژول‌های زیر استفاده کرده‌ایم. شما می‌توانید این شبکه را با هر زبان دلخواهی پیاده کنید. دلیل استفاده از پایتون فقط به دلیل در دسترس بودن این زبان برای من بوده است.ماژول PIL برای ذخیره سازی عکس‌های ایجاد شده استفاده شده است و نقش مهمی در برنامه ندارد.اطلاعات شبکه را در آرایه‌های کتابخانه numpy ذخیره کرده‌ایم.import numpy as np from random import randrange from PIL import Imageساختار شبکه:ورودی شبکه یک بردار با اندازه سه است که سه مقدار RGB در آن قرار دارد. شبکه را یک نقشه ۲ بعدی با ابعاد ۴۰x۴۰ در نظر می‌گیریم (یعنی ۱۶۰۰ نورون).قدم اول ایجاد یک عکس تصادفی:در اولین مرحله یک عکس با مقادیر RGB تصادفی ایجاد می‌کنیم. شما می‌توانید از یک عکس واقعی استفاده کنید و این مرحله را در نظر نگیرید. می‌خواهیم این عکس را به عنوان ورودی شبکه استفاده کنیم.def generate_random_color_image(image_shape=(40,40,3)): rnd_colors = np.zeros(image_shape, dtype='uint8') for i in range(image_shape[0]): for j in range(image_shape[1]): for k in range(3): v = randrange(0, 256) rnd_colors[i][j][k] = v return rnd_colorsخروجی تابع بالا یک آرایه چند بعدی است که می‌توانیم با دستورات زیر در یک فایل ذخیره کنیم.dataset = generate_random_color_image() img = Image.fromarray(dataset, 'RGB') img.save('random.png')پیاده سازی شبکه:همان طور که گفتیم اطلاعات شبکه را در یک آرایه چند بعدی ذخیره می‌کنیم. این اطلاعات همان بردار‌های وزن مربوط به هر یک از نورون‌ها است. ابعاد شبکه در متغیر map_shape تعریف شده است. این متغیر یک نقشه ۴۰ در ۴۰ که یک بردار با اندازه ۳ برای هر نورون در نظر گرفته شده است را نشان می‌دهد.در این پیاده سازی مقدار دهی‌اولیه به صورت تصادفی صورت گرفته است.map_shape = (40, 40, 3) nodes = np.random.randint(256, size=map_shape).astype(float)در ادامه باید BMU را مشخص کنیم. کل فرآیند آموزش به تعداد مشخصی epoch طول می‌کشد که شما می‌توانید این مقدار را تعیین کنید. سپس در هر epoch تک تک پیکسل‌های عکس ورودی را به شبکه نشان می‌دهیم. سپس فاصله بردار ورودی را از بردار وزن هر نورون را محاسبه می‌کنیم و نزدیک‌ترین نورون را برمی‌گزینیم. در کد زیر، مختصات نورون BMU را در متغیر winner نگه‌داشته‌ایم.for e in range(epochs): print('epoch:', e+1) for i in range(dateshpae[0]): for j in range(dateshpae[1]): # find nearest row = 0 col = 0 min_value = np.linalg.norm(dataset[i][j] - nodes[row][col]) for r in range(map_shape[0]): for c in range(map_shape[1]): dist = np.linalg.norm(dataset[i][j] - nodes[r][c]) if dist < min_value: min_value = dist row = r col = c winner = (row, col)در ادامه پس از مشخص شدن BMU باید وزن نورون‌ها را بروز رسانی کنیم.در کد زیر فاصله هر نورون روی نقشه ۲ بعدی از BMU محاسبه شده است و به عنوان ورودی به تابع neighborhood_func داده شده است (تابع همسایگی مورد نظر). علاوه بر فاصله دو نورون شماره epoch هم به تابع همسایگی داده شده است تا به مرور زمان شعاع همسایگی کاهش پیدا کند. (همان طور که در بالا اشاره کرده‌ایم.) # update weights for node in n: dist = ((winner[0] - node[0]) ** 2 + (winner[1] - node[1]) ** 2) ** 0.5 delta = learning_rate \ * neighborhood_func(dist, e) \ * (dataset[i][j] - nodes[node[0]][node[1]]) new_value = nodes[node[0]][node[1]] + delta nodes[node[0]][node[1]] = new_valueتابع همسایگی به صورت زیر تعریف گشته است. یک تابع گوسی که شعاع آن با افزایش epoch کاهش می‌یابد.def neighborhood_func(dist, epoch): sigma = 255 * 4 / ((epoch + 1) ** 2) value = np.exp(-(dist * dist) / (2 * sigma)) return valueدر نهایت می‌توانیم از تابعی که برای آموزش شبکه پیاده کرده‌ایم استفاده کنیم و خروجی آن را به صورت یک تصویر نمایش دهیم تا یک نمایش از پراکندگی طیف رنگ‌های استفاده شده در عکس ورودی داشته باشیم.sofm = kohonen(dataset) sofm_img = Image.fromarray(sofm, 'RGB') sofm_img.save('SOFM.png')شما می‌توانید کد پیاده شده را در اینجا مشاهده کنید.نتیجه‌گیریدر این نوشتار به معرفی شبکه عصبی Kohonen به صورت خلاصه پرداخته شد. این شبکه، یک شبکه‌ی Self Organizing Feature Map است. ساختار این شبکه مطرح گشت و مراحل مختلف فرآیند یادگیری آن بررسی شد. در ادامه یک مثال از پیاده سازی این شبکه عصبی مصنوعی مطرح گشت. درنهایت امیدوارم که مطالب مفید و مورد استفاده قرار گرفته باشد.