PL
 |
EN
Ograniczanie wyników
Czasopisma help
  1. 4 Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
  2. 3 Annals of Computer Science and Information Systems
  3. 3 Fundamenta Informaticae
  4. 2 Journal of Applied Computer Science
  5. 2 Logistyka
Więcej...
Autorzy help
  1. 2 Chmiel W.
  2. 2 Kadłuczka P.
  3. 2 Laszczyk Maciej
  4. 2 Myszkowski Paweł B.
  5. 2 Nagórny Z.
Więcej...
Lata help
  1. 1 2020
  2. 4 2019
  3. 2 2018
  4. 2 2017
  5. 1 2016
Więcej...
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 25

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  travelling salesman problem
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available remote Stochastic multi-depot vehicle routing problem with pickup and delivery: an ILS approach
Rios Brenner H. O., Xavier Eduardo C., Miyazawa Flávio K., Amorim Pedro
Annals of Computer Science and Information Systems
|
2020
|
Vol. 21
307--315
EN
We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery (MDVRPPD). In this paper, we present a variation of this deterministic problem, where each pair of pickup and delivery points are present with some probability, and their realization are only known after the routes are computed. We denote this stochastic version by S-MDVRPPD. One route for each depot must be computed satisfying precedence constraints, where each pickup point must appear before its delivery pair in the route. The objective is to find a solution with minimum expected traveling distance. We present a closed-form expression to compute the expected length of an a priori route under general probabilistic assumptions. To solve the S-MDVRPPD we propose an Iterated Local Search (ILS) that uses the Variable Neighborhood Descent (VND) as local search procedure. The proposed heuristic was compared with a Tabu Search (TS) algorithm based on a previous work. We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances. The results show that the ILS proposed is efficient and effective to solve S-MDVRPPD.
2
Content available Minimum Bend Shortest Rectilinear Route Discovery for a Moving Sink in a Grid Based Wireless Sensor Network
Thomas Sanu, Mathew Thomaskutty
International Journal of Electronics and Telecommunications
|
2019
|
Vol. 65, No. 2
267--276
EN
In a rectilinear route, a moving sink is restricted to travel either horizontally or vertically along the connecting edges. We present a new algorithm that finds the shortest round trip rectilinear route covering the specified nodes in a grid based Wireless Sensor Network. The proposed algorithm determines the shortest round trip travelling salesman path in a two-dimensional grid graph. A special additional feature of the new path discovery technique is that it selects that path which has the least number of corners (bends) when more than one equal length shortest round trip paths are available. This feature makes the path more suitable for moving objects like Robots, drones and other types of vehicles which carry the moving sink. In the prosed scheme, the grid points are the vertices of the graph and the lines joining the grid points are the edges of the graph. The optimal edge set that forms the target path is determined using the binary integer programming.
3
Content available remote The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
Cooper James, Nicolescu Radu
Fundamenta Informaticae
|
2019
|
Vol. 164, nr 2-3
157--180
EN
The Hamiltonian Cycle Problem (HCP) and Travelling Salesman Problem (TSP) are long-standing and well-known NP-hard problems. The HCP is concerned with finding paths through a given graph such that those paths visit each node exactly once after the start, and end where they began (i.e., Hamiltonian cycles). The TSP builds on the HCP and is concerned with computing the lowest cost Hamiltonian cycle on a weighted (di)graph. Many solutions to these problems exist, including some from the perspective of P systems. For the TSP however, almost all these papers have combined membrane computing with other approaches for approximate solution algorithms, which is surprising given the plethora of P systems solutions to the HCP. A recent paper presented a brute-force style P systems solution to the TSP with a time complexity of O(n2), exploiting the ability of P systems to reduce time complexity in exchange for space complexity, but the resultant system had a fairly high number of rules, around 50. Inspired by this paper, and seeking a more concise representation of an exact brute-force TSP algorithm, we have devised a P systems algorithm based on cP systems (P systems with Complex Objects) which requires five rules and takes n + 3 steps. We first provide some background on cP systems and demonstrate a fast new cP systems method to find the minimum of a multiset, then describe our solution to the HCP, and build on that for our TSP algorithm. This paper describes said algorithms, and provides an example application of our TSP algorithm to a given graph and a digraph variant.
4
Content available remote Non-dominated sorting tournament genetic algorithm for multi-objective travelling salesman problem
Myszkowski Paweł B., Laszczyk Maciej, Dziadek Kamil
Annals of Computer Science and Information Systems
|
2019
|
Vol. 18
67--76
EN
A Travelling Salesman Problem (TSP) is an NP-hard combinatorial problem that is very important for many real-world applications. In this paper, it is shown, that proposed approach solves multi-objective TSP (mTSP) more effectively than other investigated methods, i.e. Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed methods use rank and crowding distance (well-known from NSGA-II), combining those mechanisms in a novel, unique way: competing and co-evolving in the evolution process. The proposed modifications are investigated and verified by the benchmark mTSP instances, and results are compared to other methods.
5
Content available remote A Specialized evolutionary approach to the bi-objective travelling thief problem
Laszczyk Maciej, Myszkowski Paweł B.
Annals of Computer Science and Information Systems
|
2019
|
Vol. 18
47--56
EN
In the recent years, it has been shown that real world-problems are often comprised of two, interdependent subproblems. Often, solving them independently does not lead to the solution to the entire problem. In this article, a Travelling Thief Problem is considered, which combines a Travelling Salesman Problem with a Knapsack Problem. A Non-Dominated Sorting Genetic Algorithm II (NSGA-II) is investigated, along with its recent modification - a Non-Dominated Tournament Genetic Algorithm (NTGA). Each method is investigated in two configurations. One, with generic representation, and genetic operators. The other, specialized to the given problem, to show how the specialization of genetic operators leads to better results. The impact of the modifications introduced by NTGA is verified. A set of Quality Measures is used to verify the convergence, and diversity of the resulting PF approximations, and efficiency of the method. A set of experiments is carried out. It is shown that both methods work almost the same when generic representation is used. However, NTGA outperforms classical NSGA-II in the specialized results.
6
Content available Równoległa realizacja przykładowego algorytmu genetycznego z wykorzystaniem akceleratorów GPU
Ratuszniak P., Stasiak A., Łańcucki R.
Zeszyty Naukowe Wydziału Elektroniki i Informatyki Politechniki Koszalińskiej
|
2018
|
Nr 13
63--78
PL
W artykule zaprezentowano praktyczną implementację aplikacji rozwiązującej przykładowy algorytm genetyczny z wykorzystaniem akceleratorów GPU. W tym przypadku zdecydowano się na rozwiązanie za pomocą algorytmu genetycznego typowego problemu optymalizacyjnego, jakim jest problem komiwojażera. Dodatkowo w celu wykorzystania mocy karty graficznej w tworzonej aplikacji wykorzystano technologię programowania na karcie graficznej – technologię Nvidia CUDA.
EN
The paper presents a practical implementation of a local desktop application that solves exemplary genetic algorithm with the use of GPU accelerators. In this case decided with the use of genetic algorithm to solve typical optimization problem which is travelling salesman problem. Additionally used Nvidia CUDA programming technology in order to use power of GPU in created application.
7
Content available remote Problem komiwojażera – studium przypadku
Ziółkowski Jarosław, Miziołek Angelika, Ćwik Dariusz
Systemy Logistyczne Wojsk
|
2018
|
Vol. 49, no. 2
236--245
PL
W artykule przedstawiono problem komiwojażera na przykładzie liczbowym. Celem jest znalezienie trasy łączącej wszystkie miasta, która całościowo jest najkrótsza, najszybsza lub najtańsza i ponadto zaczyna się i kończy się w określonym punkcie. Jest to typowe zagadnienie optymalizacyjne, w którym zadane jest n miast, które komiwojażer musi odwiedzić. Jego rozwiązanie polega na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
EN
The paper presents the travelling salesman problem (TSP) on a numerical example. The aim of the paper is to find the shortest, the fastest and the cheapest route, which links all the cities and additionally starts and ends at a particular point. This is the typical optimization problem with n number of cities that the travelling salesman has to visit. The solution of the problem is to find the minimum Hamiltonian cycle in a complete weighted graph.
8
Content available Interfejs do zdalnego sterowania ploterem z funkcją rozpoznawania obrazów
Kamiński M., Morawiec M.
Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej
|
2017
|
Nr 57
37--42
PL
Maszyny numeryczne takie jak obrabiarki CNC, plotery czy drukarki 3D są coraz powszechniejsze w użytku. Na Politechnice Gdańskiej przygotowano pracę magisterską [12], której rezultaty przedstawiono w niniejszym artykule. Ze względu na objętość referatu, przedstawiono jedynie wybrane aspekty budowy plotera, aplikacji na urządzenie mobilne oraz przegląd zastosowanych algorytmów optymalizacji pod kątem szybkości rysowania. Aplikacja funkcjonuje w systemie Android, a komunikuje się z maszyną za pomocą interfejsu bluetooth. Aplikacja oferuje także możliwość optymalizacji tras, zarówno tych rysowanych, jak i nierysowanych, pokonywanych przez ploter. Jest to problem komiwojażera bez powrotu, który rozwiązany może być poprzez algorytmy: zachłanny, genetyczny, wspinaczkowy lub symulowanego wyżarzania.
EN
The topic is to build a CNC machine working as a plotter, and also create an application running on the Android operating system, which processes images, optimizes the code and allows to control the built machine. The examination is an estimation which of the methods used in this thesis is optimal and gives the best results in this type of problem, which is choosing the shortest path of the salesman problem. The purpose of the paper is to obtain the code processed by the numerical machine in the shortest possible time, which will be carried out in a short period of time with the proper accuracy of the work. Another important aspect is the implementation of an intuitive user interface that does not cause problems with support. The optimization methods used produce satisfactory results that are more or less practical depending on the problem. The effect in the form of drawn images is at a high level of accuracy. After many hours of working with the CNC machine using the created application, it can be seen that this is a useful set for both people who want to create their own images as well as for those seeking education in this field. The great advantage is that the design is very easily expandable so that it can acquire new, very useful features for a small amount of extra work in the form of adding new functionality.
9
Content available remote Zastosowanie sztucznego systemu immunologicznego do rozwiązania wielokryterialnego problemu dystrybucji dostaw
Mrówczyńska B.
Prace Naukowe Politechniki Warszawskiej. Transport
|
2017
|
z. 117
219--228
PL
W artykule przedstawiono rozwiązanie problemu znanego jako zadanie komiwojażera. Prezentowany problem polega na minimalizacji kosztów dystrybucji dostaw do wielu odbiorców obsługiwanych przez flotę pojazdów. W rozwiązaniu tego zadania bierze się pod uwagę całkowitą długość drogi, czas przejazdu i wielkości ładunku. W obliczeniach zastosowano dwie metody rozwiązania. W pierwszej z nich wyznaczono trasy wszystkich pojazdów dostawczych biorących udział w bieżącej dostawie, uwzględniając przy tym kryteria na minimum długości drogi i czasu przejazdu oraz obsługi przy ograniczeniu na ładowność pojazdów. W drugiej z metod przeprowadzono najpierw klasteryzację punktów dostaw ze względu na minimum długości drogi i ograniczenie ładowności pojazdu przeznaczonego do obsługi danego klastra dla zadanej liczby i ładowności pojazdów. Następnie dla każdego pojazdu wyznaczono najkrótszą i najszybszą drogę przez wszystkie punkty klastra, do którego był przydzielony. We wszystkich opisanych tu obliczeniach zastosowano algorytmy sztucznych systemów immunologicznych. Problemy wielokryterialne został rozwiązane metodą kryteriów ważonych i optymalności Pareto.
EN
In the paper the solution of the issue known as a traveling salesman problems (TSP) is presented. A minimizing of costs of distributing supplies to multiple recipients supported by a fleet of vehicles is considered. the total path length, the driving time and the volumes of cargo is taken into account in the solution of the task . An artificial immune system is used to solve it. This multi-criteria problem has been solved using objectives weighted method and Pareto efficiency. Results were compared.
10
Content available remote A comparison of ant colony optimization and genetic algorithm for solving the traveling salesman problem
Ochelska-Mierzejewska J.
Journal of Applied Computer Science
|
2016
|
Vol. 24, nr 1
51--66
EN
Every company in today’s world faces the constant challenge of cost reduction. For distribution and transport service providers, cost cutting appears to be the main operational goal. The successful companies seek to develop an optimal routes for their fleets to minimize the costs and guarantee a timely delivery of the goods. With a growing informatization of the industrial world, it is worth considering the use of intelligent systems as a possible way of solving various types of decision problems, which in turn can contribute to the reduction of costs incurred by a company. Such systems enable multidimensional data analysis and to provide information useful in decision making. The paper investigates the use of the genetic algorithm and the ants colony optimization algorithm as a solution to the travelling salesman problem. It has been shown that both methods provide satisfactory results in solving the problem under examination.
11
Wybrane zagadnienia optymalizacji transportu odpadów komunalnych
Pawul M., Kwiecień J., Śliwka M.
Logistyka
|
2015
|
nr 4
9585--9592, CD3
PL
Gospodarowanie odpadami wymaga rozwiązań skutecznych pod względem ochrony środowiska, ale także efektywnych ekonomicznie. Spośród wszystkich etapów gospodarowania odpadami komunalnymi, dużą część kosztów generuje ich transport pomiędzy punktami zbiórki a miejscem ich przetwarzania. Opierając się na danych literaturowych zaprezentowano różne modele i metody stosowane do wyboru najkorzystniejszej trasy przejazdu śmieciarek, w tym problemy trasowania z żądaniami zlokalizowanym w wierzchołkach lub na krawędziach czy łukach grafu.
EN
Waste management requires effective solutions in terms of environmental protection, and also cost-effective. Among all stages of municipal waste management, transport between collection points and the place of processing, generates a large part of the costs. Based on the literature, different models and methods used for selecting the best route of garbage trucks, including node routing problems and arc routing problems, are presented.
12
Content available W poszukiwaniu optymalnej trasy – wybrane algorytmy w zastosowaniu do problemu komiwojażera
Jakubowska A., Piechocka K.
Journal of TransLogistics
|
2015
|
Vol. 1, nr 1
7--24
PL
Ze względu na dążenie do ograniczenia kosztów logistycznych przedsiębiorstw coraz większego znaczenia nabiera zagadnienie optymalizacji tras. Coraz częściej wykorzystuje się w tym celu rozwiązania heurystyczne oparte na sztucznej inteligencji. Uwzględniając duży stopień trudności w tym zakresie, szczególnie istotne jest wykorzystanie wsparcia informatycznego. Niniejsza praca przedstawia problem komiwojażera oraz możliwość jego rozwiązania za pomocą algorytmów heurystycznych. Szerzej zaprezentowano algorytmy mrówkowy oraz genetyczny.
EN
Due to striving for reducing the logistic cost of enterprises, the route optimisation issue becomes more and more important. For this purpose heuristic solutions based on artificial intelligence are often used. Taking into account the high difficulty of optimization problems, it is particularly important to use IT support. This paper presents the Traveling Salesman Problem and the idea of heuristic algorithms used to solve this problem. More detailed were presented Ant Colony Optimization Algorithm and Genetic Algorithm.
13
Content available Aplikacja wyszukiwania i wizualizacji trasy dla przewoźników samochodowych
Ratuszniak P., Gątnicki Ł.
Zeszyty Naukowe Wydziału Elektroniki i Informatyki Politechniki Koszalińskiej
|
2013
|
Nr 5
115--125
PL
W artykule zaprezentowano praktyczną implementację algorytmu genetycznego do rozwiązywania problemu optymalizacji trasy analogicznego do problemu komiwojażera. Algorytm został zaimplementowany w autorskiej aplikacji do wyznaczania trasy przejazdu dla rzeczywistych danych geograficznych polskich miejscowości pobieranych z serwisu Google Maps. Prezentowana aplikacja generuje wskazówki dojazdu i umozliwia export wyznaczonej trasy do programu Automapa, co stanowi jego doskonałe uzupełnienie.
EN
The paper presents a practical implementation of a genetic algorithm to solve the problem of route optimization analogous to the traveling salesman problem. The algorithm has been implemented in the author's application for route calculation for the real Polish geographic data retrieved from Google Maps service. Presented application generates travel directions in the text and graphic form and allows to export the computed route to the Automapa program, which is his perfect complement.
14
Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: quality, uncertainty and speed
Antosiewicz M., Koloch G., Kamiński B.
Journal of Theoretical and Applied Computer Science
|
2013
|
Vol. 7, nr 1
46--55
EN
We compare six metaheuristic optimization algorithms applied to solving the travelling salesman problem. We focus on three classical approaches: genetic algorithms, simulated annealing and tabu search, and compare them with three recently developed ones: quantum annealing, particle swarm optimization and harmony search. On top of that we compare all results with those obtained with a greedy 2-opt interchange algorithm. We are interested in short-term performance of the algorithms and use three criteria to evaluate them: solution quality, standard deviation of results and time needed to reach the optimum. Following the results from simulation experiments we conclude that simulated annealing and tabu search outperform newly developed approaches in short simulation runs with respect to all three criteria. Simulated annealing finds best solutions, yet tabu search has lower variance of results and converges faster.
15
Content available Rozwiązywanie problemu komiwojażera za pomocą Metody Ewolucyjnej z Excela 2010
Węgrzyn J.
Gospodarka Materiałowa i Logistyka
|
2013
|
nr 12
11--17
PL
W artykule przedstawiono wyniki rozwiązywania czternastu przykładów TSP (Traveling Salasman Problem) ze zbior TSPLIB w oparciu o premutacje z wykorzystaniem Metody Ewolucyjnej ze standardowego Solvera z MS Excel 2010.
EN
The results of samples solutions of Traveling Salesperson Problem (TSP) received using Evolutionary Solver included in standard Solver for MS Excel 2010 is presented in this article. According to All different constraints Evolutionary Solver permits to solve TSP based on combinatorial model using permutation. Results are samples of solutions and time values received for accepted parameters and restart manners of Solver.
16
Content available remote Accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem
Nagórny Z.
Journal of Applied Computer Science
|
2012
|
Vol. 20, nr 1
51-67
EN
The objective of this work was to study the accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem. In this work the 8-bit accuracy influence of the hardware implementation of weights, activation functions, and external input signals on the quality of achieved solutions for 100 randomly generated instances of the 10-city TSP was studied and comparable results in comparison with the simulation in which the network was simulated using double precision floating point numbers were obtained. The results show that the hardware implementation of the Hopfield network with the 8-bit accuracy allows to obtain satisfactory solutions for the TSP. It should be also noted that the network described in this work utilizes the novel method of auto-tuning of Hopfield network parameters and thanks to this method, in contrast to other works, none of the network parameters is tuned for a given solved TSP on the basis of preliminary simulations. The Hopfield network presented in this work is destined for the hardware implementation. The application of the hardware implementation of the network could significantly decrease the time required to obtain the combinatorial problem solution in comparison with methods using von Neumann architecture computers.
17
Content available Zastosowanie algorytmów rojowych w rozwiązywaniu zagadnień permutacyjnych
Chmiel W., Kadłuczka P., Packanik G.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2011
|
T. 15, z. 2
117-126
PL
W artykule przedstawiono wyniki badań nad zastosowaniem algorytmów rojowych w optymalizacji zagadnienia szeregowania zadań, jako przykładu AP-trudnego zagadnienia optymalizacyjnego. W oparciu o instancje testowe dla zagadnienia szeregowania zadań zaproponowane przez E. Taillarda, przeprowadzono eksperymenty obliczeniowe, porównując wyniki otrzymywane przez algorytm ptasi oraz algorytm pszczeli. Przebadano także wpływ implementacji poszczególnych elementów algorytmów, takich jak liczba, dokładność i sposób przeszukiwania otoczenia rozwiązań obiecujących, na uzyskiwane wyniki optymalizacji. Pozwoliło to na sformowanie ogólnych wniosków dotyczących własności obu algorytmów.
EN
The objective of this paper is to examine the most important properties of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and a method for migrant selection. A short review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. The proposed measure has proved effective in helping to retain balance between population diversity and convergence. A multi-population genetic algorithm, with different parameters like type of topology, migration interval, migration size and selection method was tested against several different test instances of traveling salesman problem, that belongs to the NP-hard permutational problem class.
18
Content available Efektywność wielopopulacyjnego algorytmu ewolucyjnego dla zagadnień permutacyjnych
Filipowicz B., Chmiel W., Dudek M., Kadłuczka P.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2011
|
T. 15, z. 2
147-158
PL
W artykule przedstawiono wyniki badań najistotniejszych elementów wielopopulacyjnego algorytmu ewolucyjnego. W zastosowanym modelu wyspowym należą do nich: topologia połączeń, rozmiar i częstotliwość migracji oraz metoda selekcji migrantów. Zaproponowana miara różnorodności populacji może być wykorzystywana dla szerokiej klasy zagadnień permutacyjnych, których przykładem jest rozważane zagadnienie komiwojażera (TSP). Badania eksperymentalne przeprowadzono dla standardowych zagadnień testowych zaczerpniętych z biblioteki TSPLib95.
EN
The objective of this study is to examine the most important traits of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and migrant seleetion method. A review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. It has proved effective in helping to retain balance between population diversity and convergence. For each trait, several algorithm configurations have been tested. Every configuration was tested against 25 different test instances, which were derived from the TSPLib95 library. Test results showed that, among the tested parameters, the most important was topology. Of the eleven topologies, a circular (ring) topology consisting of 16 islands obtained the best results. Varying of migration interval showed little correlation with the solution quality, but it did affect the convergence time. In comparison to other parameters, migration size exerts a relatively strong influence on performance. Moreover, a medium migration size proved to be reasonable. Among migrant selection methods, random selection outperformed these methods that exert selective pressure.
19
Usprawnianie procesów transportowych z wykorzystaniem usług sieciowych na przykładzie przedsiębiorstwa komunalnego
Karkula M., Szymanowska A.
Logistyka
|
2010
|
nr 2
PL
Celem artykułu jest analiza wybranych procesów z zakresu transportu miejskiego i propozycja nowego rozwiązania, które ma za zadanie zminimalizować liczbę przejazdów w obszarach aglomeracji oraz odciążyć miasto od zbędnego transportu. Zaproponowane rozwiązanie łączy wykorzystanie metod optymalizacji kombinatorycznej z usługami sieciowymi Google Maps.
EN
Aim of this study is to analyze selected processes in the field of urban transport and to propose a new solution that aims to minimize the number of trips in urban areas and relieve the city from the unnecessary transport. The proposed solution combines the use of combinatorial optimization methods and web services such as Google Maps.
20
Content available remote Optymalizacja z wykorzystaniem zmodyfikowanej sieci Hopfielda
Nagórny Z., Kos A.
Kwartalnik Elektroniki i Telekomunikacji
|
2005
|
Vol. 51, z. 2
255--275
PL
W pracy przedstawiono oryginalną metodę rozwiązywania problemów optymalizacyjnych z wykorzystaniem zmodyfikowanej sieci neuronowej typu Hopfielda. W klasycznym rozwiązaniu wartości wag połączeń między neuronami w sieci Hopfielda są obliczane przed symulacją i nie ulegają zmianie. W niniejszej pracy zbadano wpływ modyfikacji wartości sygnałów wejściowych neuronów lub wag podczas symulacji sieci, na otrzymywane rozwiązania. Zauważono, że modyfikacja sygnałów wejściowych lub wag umożliwia uzyskanie lepszych rozwiązań. W pracy przedstawiono rezultaty otrzymane zmodyfikowaną siecią dla problemu komiwojażera. Dla problemów o wymiarze równym 10, sieć dla 100% prób generowała optymalne rozwiązanie. Dla większych problemów rozwiązania są lepsze od otrzymanych klasyczną siecią. Przedstawiono wnioski płynące z zastosowania opisanej metody.
EN
The paper presents a novel method for solving optimization problems by using a modified Hopfield network. In a conventional Hopfield network weight values of the net are calculated before simulation and are constant. Our method is a novel method, because the values of input signals or weights are modified during simulation. The method makes use of the Hopfield net with continuous function of neurons according to Eq. (2). The model Hopfield net in electronic components is shown in Figure 1. An energy function of the neural net is described by Eq. (3). Comparing Eq. (3) and Eq. (4), which is a general form of an optimization problem cost function, we get weight and external input signal values. The Hopfield net is implemented in software in this work. A simulating program makes use of Eq. (11) to calculate the input of each neuron in the net. During the simulation the input signals are modified in accordance with Eq. (12). The duration of input signals modifying is defined by a random value nnar. Finally, a number of iterations to achieve a stable state of the net are done. A number of trials are performed for each optimization problem and the best results are chosen. Figure 2 shows the algorithm of the method. In this work, simulations were done for six examples of the travelling salesman problem. A cost function of the travelling salesman problem is described by Eq. (17). This function consists of four components: the total length of the salesman's tour, two terms, which ensure that the salesman's tour is valid and the term, which forces neurons to have the output signal equal zero or one. The method with input signal values modifying during simulation gives better results than the conventional one. Results are performed in Table 1 and 2. For ten-city problems the modified Hopfield net finds the optimal solution with 100% success rate. Some conclusions coming from using this method are presented.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.