Ett kommunikationsnät kan illustreras med en uppsättning noder (eller växlar) och länkar (eller bågar) där alla noder är anslutna via länkar. Den typiska strukturen för kommunikationsnätverk består av två nivåer. Den första är stamnätet och den andra är det lokala accessnätet (LAN). Stomnäten ägnar sig åt att leverera information från källa till destination (slut till slut) med hjälp av sina kopplingsnoder. LAN är typiskt centraliserat system som gör det möjligt för användare att komma åt värdar eller lokala servrar. Detta kapitel fokuserar endast på den stamnätsdesign som betraktas som distribuerat nät. Tillkomsten av lågkostnadsutrustning har lett till en explosionsartad ökning av kommunikationsnäten. Topologin nätverksdesign är en del av nätverksplanering som finner en topologi för att uppfylla eventuella begränsningar. En av de största fördelarna med distribuerade nät över det centraliserade systemet är deras flexibilitet för att förbättra systemets tillförlitlighet. Ett systems tillförlitlighet beror inte bara på tillförlitligheten hos dess noder och länkar, utan också på nätets topologi. Ett helt uppkopplat nät har den högsta nättillförlitligheten medan det enkla nätet (ringnätet) har den lägsta nättillförlitligheten. Många forskare har studerat nätverkets utformning när man betraktar systemets tillförlitlighet som en begränsning eller ett mål. De tillförlitliga nätkonstruktionsproblemen visar sig vara källsänka och helt slutna näts tillförlitlighet (även känd som total tillförlitlighet). Problemet med optimal topologi nätverksdesign som väljer de länkar anslutningar som antingen maximerar tillförlitligheten eller minimerar kostnaden kan formulera som ett kombinatoriellt problem. Detta problem är ett välkänt NP-hard problem och mycket svårt att lösa. För sådana problem har många forskare studerat med uppräkningsbaserad och heuristisk metod. Jan (1993) utvecklade en algoritm med hjälp av nedbrytning baserad på varumärke och bunden att minimera länkkostnaden för kommunikationsnät under förutsättning att tillförlitligheten begränsas. Aggarwal m.fl. (1982) använde sig av girig heuristisk metod för att maximera tillförlitligheten med tanke på en kostnadsbegränsning för nätverk med olika pålitlighet av länkar och noder. Pierre m.fl. (1995) Man använde sig också av simulerad glödgning för att hitta den optimala konstruktionen för nät för paketbyte, med tanke på fördröjningen och kapaciteten, men inte tillförlitligheten. För nätverksdesignen Kumar et al. (1995) utvecklade en genetisk algoritm (GA) med hänsyn till diameter, medelavstånd och kommunikationsnätverkstillförlitlighet och tillämpade den på fyra testproblem på upp till nio noder. med alternativa länkars tillförlitlighet och alla slutna näts tillförlitlighetsbegränsningar. Dessutom, Glover et al. (1991) Använda tabusökningsalgoritm (TS) för att välja nätets topologier när man överväger kostnader och kapacitet, men inte tillförlitlighet. Ett annat arbete med TS-algoritm, Beltran & Skorin-Kapov (1994) använde TS-algoritm för att utforma tillförlitliga nätverk genom att söka efter de lägsta kostnaderna för tvåträd, där tvåträdsmålet var en grov surrogat för tillförlitlighet. Nyligen har moderna heuristiska optimeringsmetoder såsom simulerad glödgning (SA), GA, evolutionär programmering (EP), TS-algoritm, artificiellt neuralt nätverk (ANN), partikelsvärmoptimering (PSO) och optimering av myrkolonier (ACO) ägnats stor uppmärksamhet av många forskare på grund av deras förmåga att hitta en nästan global optimal lösning. Bland annat förväntade sig TS-algoritmen som en av de avancerade sökteknikerna. TS-algoritmen kan fly från lokal optimal och snabbt konvergera till global optimal. En konventionell TS-algoritm kan dock ha problem med att nå den globala optimala lösningen inom en rimlig beräkningstid när den ursprungliga lösningen ligger långt från den region där optimal lösning finns. Numera har persondatorn mer snabba beräkningar. För att lösa det storskaliga problemet kan flera datorer använda för beräkning samtidigt. Denna metod kallas "parallell sökningar". Å andra sidan utförs "multipel sökning" i detta kapitel endast av en persondator. Flera sökningar hjälper till att hitta den lovande regionen där den globala optimala lösningen finns. Denna idé gäller för att förbättra prestandan för en konventionell TS-algoritm. Pothiya m.fl. (2006) utvecklade flera tabusökningsalgoritm (MTS) och tillämpade denna algoritm för att designa den optimala luddiga logiken PI controller. Efter det, MTS tillämpas för att lösa det ekonomiska leveransproblemet med generatorrestriktion (Pothiya et al., 2008). MTS är körningen av enskilda TS-algoritmer samtidigt med endast en persondator. Genom MTS införs ytterligare viktiga mekanismer för att förbättra sökprocessen, dvs. initiering, adaptiv sökning, flera sökningar, ersätta och starta om processen. Genomförbarhetsstudien av MTS för detta kapitel visade för att lösa topologin nätverksdesign när man överväger både tillförlitlighet och kostnad. De optimerade resultaten från MTS jämfört med de som erhållits genom konventionella metoder som GA, TS och ACO när det gäller lösningskvalitet och beräkningseffektivitet. Återstoden av detta kapitel organiserar sig enligt följande. I avsnitt 2 beskrivs problemformulering, systemantaganden och beräkning av tillförlitlighet. I avsnitt 3 presenteras principen om MTS-algoritm för att lösa topologins nätverksdesign. I avsnitt 4 visas exempel och simuleringsresultat. Slutligen innehåller avsnitt 5 diskussion och slutsats.
Dessutom användes Multipel TS-algoritm REF för att lösa NTD-CR-problemet med 19 noder, men algoritmen kanske inte når den globala optimala lösningen under en rimlig beräkningstid när den ursprungliga lösningen är långt borta från den region där den optimala lösningen finns.
Multiple Tabu Search Algorithm for Solving the Topology Network Design
{'venue': 'Tabu Search', 'journal': 'Tabu Search', 'mag_field_of_study': ['Computer Science']}