एन के मॉडल

एनके (NK) मॉडल एक गणितीय मॉडल है जिसे इसके प्राथमिक आविष्कारक स्टुअर्ट कॉफ़मैन ने एक ''ट्यूनेबली रगेड'' फिटनेस परिदृश्य के रूप में वर्णित किया है। ''ट्यूनेबल रुग्गड़नेस'' ट्यून करने योग्य असभ्यता इस अंतर्ज्ञान को पकड़ती है कि परिदृश्य के समग्र आकार और इसकी स्थानीय ''पहाड़ियों और घाटियों'' की संख्या दोनों को इसके दो मापदंडों में परिवर्तन के माध्यम से समायोजित किया जा सकता है, $N$ और $K$, साथ $N$ विकास की एक श्रृंखला की लंबाई होने के नाते और $K$ भूदृश्य की रगेडनेस के स्तर का निर्धारण है।

एनके मॉडल ने विभिन्न प्रकार के क्षेत्रों में आवेदन पाया है, जिसमें विकासवादी जीव विज्ञान, इम्मुनोलोगि, संयुक्त अनुकूलन, तकनीकी विकास और सम्मिश्र प्रणालियों का सैद्धांतिक अध्ययन सम्मिलित है। मॉडल को संगठनात्मक सिद्धांत में भी अपनाया गया था, जहां इसका उपयोग यह वर्णन करने के लिए किया जाता है कि कैसे एक एजेंट-आधारित मॉडल स्वयं की विभिन्न विशेषताओं में हेरफेर करके एक परिदृश्य की खोज कर सकता है। उदाहरण के लिए, एक एजेंट एक संगठन हो सकता है, पहाड़ियाँ और घाटियाँ लाभ(अर्थशास्त्र) (या उसमें परिवर्तन) का प्रतिनिधित्व करती हैं, और परिदृश्य पर आंदोलन के लिए संगठनात्मक निर्णयों की आवश्यकता होती है (जैसे कि उत्पाद लाइनें जोड़ना या संगठनात्मक संरचना में बदलाव करना), जो इंटरैक्ट (परस्पर क्रिया) करते हैं एक दूसरे के साथ और सम्मिश्र तरीके से लाभ को प्रभावित करते हैं।

मॉडल का प्रारंभिक संस्करण, जिसे केवल सबसे सहज माना जाता था ($K=0$) और सबसे  रगेड (ऊबड़-खाबड़) ($K=N-1$) परिदृश्य, कॉफ़मैन और लेविन (1987) में प्रस्तुत किया गया था। जिस मॉडल को वर्तमान में जाना जाता है वह पहली बार कॉफ़मैन और वेनबर्गर (1989) में दिखाई दिया।

मॉडल ने कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में व्यापक ध्यान आकर्षित किया है, इसका एक कारण यह है कि यह तथाकथित एनपी-पूर्ण समस्या का एक विशेष रूप से सरल उदाहरण है। जिसका अर्थ है कि वैश्विक ऑप्टिमा खोजना कठिन है। हाल ही में, यह दिखाया गया कि K > 1 के लिए एनके मॉडल भी पीएलएस (जटिलता) पीएलएस-पूर्ण है जिसका मतलब है कि, सामान्य तौर पर, स्थानीय फिटनेस ऑप्टिमा भी ढूंढना कठिन है। ओपन-एंडेड विकास के अध्ययन के लिए इसके परिणाम हैं।

प्रोटोटाइपिक उदाहरण: प्लाज्मिड फिटनेस

प्लास्मिड कुछ कोशिकाओं के अंदर डीएनए का एक छोटा चक्र है जो अपने मेजबान कोशिकाओं से स्वतंत्र रूप से दोहरा सकता है। मान लीजिए हम प्लास्मिड की उपयुक्तता का अध्ययन करना चाहते हैं।

सरलता के लिए, हम एक प्लास्मिड को हमेशा एक ही क्रम में N संभावित जीन की रिंग के रूप में मॉडल करते हैं, और प्रत्येक में दो संभावित अवस्थाएं हो सकती हैं (सक्रिय या निष्क्रिय, प्रकार X या प्रकार Y, आदि...)। फिर प्लास्मिड को लंबाई N के साथ एक बाइनरी कोड स्ट्रिंग द्वारा मॉडल किया जाता है, और इसी तरह फिटनेस फ़ंक्शन होता है $F:\{0,1\}^{N}\to \mathbb {R}$.

सबसे सरल मॉडल में जीन एक-दूसरे के साथ इंटरैक्ट नहीं करते, और इसलिए हम प्राप्त करते हैं

$$F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})$$

जहां प्रत्येक $f_{i}(S_{i})$ जीन की फिटनेस में योगदान को दर्शाता है $S_{i}$ स्थान पर $i$.

एपिस्टासिस को मॉडल करने के लिए, हम एक अन्य कारक K का परिचय देते हैं, अन्य जीनों की संख्या जिनके साथ एक जीन इंटरैक्ट करता है। यह मानना ​​उचित है कि एक प्लास्मिड पर, दो जीन इंटरैक्ट करते हैं यदि वे आसन्न हों, इस प्रकार देते हैं

$$F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1},S_{2})+f_{2}(S_{2},S_{3})+\cdots +f_{N-1}(S_{N-1},S_{N})+f_{N}(S_{N},S_{1})$$

उदाहरण के लिए, जब K = 1, और N = 5,

$F(00101)=f_{1}(0,0)+f_{2}(0,1)+f_{3}(1,0)+f_{4}(0,1)+f_{5}(1,0)$

एनके मॉडल स्वेच्छाचारी से परिमित K, N की अनुमति देकर, साथ ही जीन की आसन्नता की स्वेच्छाचारी परिभाषा की अनुमति देकर इसे सामान्य बनाता है (जीन आवश्यक रूप से एक वृत्त या रेखा खंड पर स्थित नहीं होते हैं)।

गणितीय परिभाषा

एनके मॉडल एक सांयोगिक चरण स्थान को परिभाषित करता है, जिसमें लंबाई की प्रत्येक स्ट्रिंग (किसी दिए गए वर्णमाला से चुनी गई) सम्मिलित होती है $N$l इस खोज स्थान में प्रत्येक स्ट्रिंग के लिए, एक अदिश (गणित) मान (जिसे फिटनेस कार्य कहा जाता है) परिभाषित किया गया है। यदि स्ट्रिंग के बीच एक दूरी मीट्रिक (गणित) परिभाषित की जाती है, तो परिणामी संरचना एक परिदृश्य है।

फिटनेस मूल्यों को मॉडल के विशिष्ट अवतारण के अनुसार परिभाषित किया गया है, लेकिन एनके मॉडल की मुख्य विशेषता यह है कि किसी दिए गए स्ट्रिंग की फिटनेस $S$ प्रत्येक स्थान से योगदान का योग है $f_{i}(S)$ स्ट्रिंग में:

$F(S)=\sum _{i}{\tilde {f}}_{i}(S),$

और सामान्यतः प्रत्येक लोकस का योगदान उसकी स्थिति और स्थिति पर निर्भर करता है $K$ अन्य लोकी,:

${\tilde {f}}_{i}(S)=f_{i}(S_{i},S_{k_{i1}},\dots ,S_{k_{iK}}),$

जहाँ $k_{ij}$ का सूचकांक है ${\displaystyle }$