Spelling suggestions: "subject:" metaheuristics"" "subject:" etaheuristics""
101 |
Um sistema de codificação de vídeo para TV digital – SBTVDLinck, Iris Correa das Chagas 29 June 2012 (has links)
Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2015-07-03T17:52:39Z
No. of bitstreams: 1
Iris Corrêa das Chagas Linck.pdf: 1456080 bytes, checksum: ea4a6f659a229e845649c58baaf8cb23 (MD5) / Made available in DSpace on 2015-07-03T17:52:39Z (GMT). No. of bitstreams: 1
Iris Corrêa das Chagas Linck.pdf: 1456080 bytes, checksum: ea4a6f659a229e845649c58baaf8cb23 (MD5)
Previous issue date: 2012 / FINEP - Financiadora de Estudos e Projetos / Neste trabalho é desenvolvido um algoritmo híbrido que simula o comportamento do Codificador/Decodificador de vídeo H.264/AVC, ou simplesmente CODEC H.264, utilizado no Sistema Brasileiro de Televisão Digital. O algoritmo proposto tem a finalidade de buscar a melhor configuração possível de seis dos principais parâmetros utilizados para a configuração do CODEC H.264. Este problema é abordado como um problema de otimização combinatória conhecido como Problema de Seleção de Partes e que é classificado como NP-Difícil. O algoritmo híbrido proposto, denominado Simulador de Metaheurísticas aplicado a um CODEC (SMC), foi desenvolvido com base em duas metaheurísticas: Busca Tabu e Algoritmo Genético. Os seis parâmetros de configuração a serem otimizados pelo SMC são: o bit rate; o frame rate; os parâmetros de quantização de quadros tipo B, tipo P e tipo I e a quantidade de quadros tipo B em um grupo de imagens (GOP – Group of Pictures). Os dois primeiros parâmetros mencionados atuam basicamente sobre a qualidade da imagem do vídeo enquanto que os demais parâmetros atuam diretamente na compressão do vídeo. Experimentos e testes foram feitos utilizandose o CODEC H.264 desenvolvido no Projeto Plataforma de Convergência Digital IPTV/TV Digital (DigConv). Nos experimentos o CODEC tem seus parâmetros configurados de acordo com os resultados obtidos pelo SMC. Um vídeo é codificado no CODEC H.264 para que se possa analisar a sua qualidade de imagem e o seu grau de compressão após o processo de codificação. É feita uma correlação entre esses resultados e a Função Objetivo do SMC. A qualidade da imagem é medida através da métrica mais utilizada na literatura, o PSNR (Peak Signal to Noise Ratio), que é calculada pelo próprio CODEC ao final da codificação de um vídeo. Verificouse que à medida que a Função Objetivo aumenta, o CODEC H.264 consegue obter uma melhor qualidade de imagem e um maior grau de compressão de vídeo. / In this work is developed a hybrid algorithm that simulates the behavior of the H.264/AVC video encoder/decoder, or simply H.264 video CODEC, used in the Brazilian System of Digital Television. The proposed algorithm intends to seek the best possible configuration of the six main parameters used for configuring the H.264 video CODEC. This problem is treated as a combinatorial optimization problem known as the Parties Selection Problem, which is classified as NP-Hard. The proposed hybrid algorithm, called Simulator Metaheuristcs applied to a CODEC (SMC), was developed based on two metaheuristics: Tabu Search and Genetic Algorithm. The six configuration parameters to be optimized by the SMC are the bit rate, frame rate, the parameters of quantization tables of type B, type I and type P and the amount of frames type B in a group of pictures (GOP - Group of Pictures).The first two parameters mentioned, work primarily on the quality of the video image while the other parameters act directly on the video compression. Experiments and tests were done using the video CODEC H.264 developed in Digital Convergence Platform IPTV/Digital TV Project (DigConv). DigConv Project. In the experiments the CODEC has its parameters set according to the results obtained by the SMC. Then, a video is encoded by the CODEC in order to analyze the video image quality and the video compression degree reached after the encoding process. It is made a correlation between these results and the objective function of the SMC. The picture quality is measured by the metric most often used in literature, the PSNR (Peak Signal to Noise Ratio), which is calculated by the CODEC at the end of a video encoding process. It was found that as the objective function has increased, the CODEC reached a better image quality and a higher video compression.
|
102 |
Meta-heurísticas bio-inspiradas para otimização multiobjetivo do controle Volt/VAr no contexto das redes elétricas inteligentes. / Bio-inspired metaheuristic applied to Volt/Var control multiobjective optimization problem in smart grid context.Medeiros, Thiago Saúde 07 June 2018 (has links)
O presente trabalho tem como objetivo comparar o desempenho de diferentes metaheurísticas bio-inspiradas aplicadas à resolução de problemas de otimização multiobjetivo do controle de tensão e reativos, ou controle Volt/VAr, em redes elétricas inteligentes. Entre os algoritmos implementados estão o algoritmo genético, o algoritmo memético, a otimização por colônia de formigas, a otimização por enxame de partículas e o strength pareto evolutionary algorithm (SPEA2). Aplicações dos algoritmos à resolução de problemas de otimização do controle Volt/VAr, em redes de distribuição de energia elétrica com dimensões reais, são utilizadas para comparação de seus indicadores de desempenho. A avaliação é feita tanto em relação à velocidade de busca quanto em relação à qualidade da solução encontrada. Os algoritmos mostraram resultados promissores para aplicação a redes de distribuição com dimensões reais, encontrando soluções de qualidade em tempos de busca aceitáveis. Parte deste desempenho se dá pelos métodos meta-heurísticos, parte por conta da modelagem adotada no processo de otimização. / The present work aims at comparing the performance of different bio-inspired metaheuristics applied to the Volt/VAr control multiobjective optimization problem in smart grids. Among the algorithms implemented are the genetic algorithm, the memetic algorithm, ant colony optimization, particle swarm optimization and the strength pareto evolutionary algorithm (SPEA2). Applications of the algorithms to solve Volt/VAr control optimization problems in distribution networks with real dimensions are used to compare their performance indicators. The evaluation is done both in relation to the search speed and in relation to the quality of the solution found. The promising results show that the algorithms are applicable to distribution networks with real dimensions, finding quality solutions in acceptable search times. This performance is obtained due to both the metaheuristic methods, and the modeling adopted in the optimization process.
|
103 |
Fluxo de potência ótimo multiobjetivo com restrições de segurança e variáveis discretas / Multiobjective security constrained optimal power flow with discrete variablesEllen Cristina Ferreira 11 May 2018 (has links)
O presente trabalho visa a investigação e o desenvolvimento de estratégias de otimização contínua e discreta para problemas de Fluxo de Potência Ótimo com Restrições de Segurança (FPORS) Multiobjetivo, incorporando variáveis de controle associadas a taps de transformadores em fase, chaveamentos de bancos de capacitores e reatores shunt. Um modelo Problema de Otimização Multiobjetivo (POM) é formulado segundo a soma ponderada, cujos objetivos são a minimização de perdas ativas nas linhas de transmissão e de um termo adicional que proporciona uma maior margem de reativos ao sistema. Investiga-se a incorporação de controles associados a taps e shunts como grandezas fixas, ou variáveis contínuas e discretas, sendo neste último caso aplicadas funções auxiliares do tipo polinomial e senoidal, para fins de discretização. O problema completo é resolvido via meta-heurísticas Evolutionary Particle Swarm Optimization (EPSO) e Differential Evolutionary Particle Swarm Optimization (DEEPSO). Os algoritmos foram desenvolvidos utilizando o software MatLab R2013a, sendo a metodologia aplicada aos sistemas IEEE de 14, 30, 57, 118 e 300 barras e validada sob os prismas diversidade e qualidade das soluções geradas e complexidade computacional. Os resultados obtidos demonstram o potencial do modelo e estratégias de resolução propostas como ferramentas auxiliares ao processo de tomada de decisão em Análise de Segurança de redes elétricas, maximizando as possibilidades de ação visando a redução de emergências pós-contingência. / The goal of the present work is to investigate and develop continuous and discrete optimization strategies for SCOPF problems, also taking into account control variables related to in-phase transformers, capacitor banks and shunt reactors. Multiobjective optimization model is formulated under a weighted sum criteria whose objectives are the minimization of active power losses and an additional term that yields a greater reactive support to the system. Controls associated with taps and shunts are modeled either as fixed quantities, or continuous and discrete variables, in which case auxiliary functions of polynomial and sinusoidal types are applied for discretization purposes. The complete model is solved via EPSO and DEEPSO metaheuristics. Routines coded in Matlab were applied to the IEEE 14,30, 57, 118 and 300-bus test systems, where the method was validated in terms of diversity and quality of solutions and computational complexity. The results demonstrate the robustness of the model and solution approaches and uphold it as an effective support tool for the decision-making process in Power Systems Security Analysis, maximizing preventive actions in order to avoid insecure operating conditions.
|
104 |
Técnicas de otimização combinatória multiobjetivo aplicadas na estimação do desempenho elétrico de redes de distribuição. / Multiobjective combinatorial optimization techniques applied on electrical performance estimation of distribution networks.Kleber Hashimoto 27 September 2004 (has links)
Neste trabalho são apresentadas contribuições para a estimação do desempenho elétrico na distribuição de energia elétrica, com implicações nos mais diversos problemas da operação e do planejamento da distribuição. Entende-se por desempenho elétrico, a avaliação dos parâmetros de congestionamento de redes, as perdas e o nível de tensão. A motivação deste trabalho está na agregação dos esforços advindos da campanha de medição compulsória das concessionárias de distribuição e da necessidade do órgão regulador de estabelecer parâmetros de avaliação do desempenho operacional das empresas, como previsto no documento intitulado Procedimentos da Distribuição da Aneel. A estimação do desempenho elétrico é formulada segundo um problema de otimização multiobjetivo onde as funções objetivo compõem uma avaliação de probabilidade de ocorrência e uma avaliação de proximidade dos parâmetros elétricos calculados com os valores obtidos por medição. Os valores das cargas são discretizados segundo probabilidades de ocorrência em cada intervalo, de modo que a formulação resulte em um problema de otimização combinatória multiobjetivo de dimensão exponencial. Propõe-se um procedimento de redução de rede, que diminua consideravelmente o espaço de decisões, e um procedimento de expansão de redes para recompô-la. Também são propostas heurísticas específicas para a obtenção de soluções com cargas diversificadas e desequilibradas. Para uma aplicação adequada destas heurísticas, propôs-se e aplicou-se um método evolucionário metaheurístico para composição das soluções factíveis, ordenadas de acordo com o conceito de dominância de Pareto. Para cada fronteira de dominância, ou conjunto de fronteiras, o aplicativo constrói a distribuição probabilística da corrente e fluxo de potência de cada trecho, o nível de tensão em todas as barras e as perdas técnicas totais do circuito. A formulação matemática de otimização é flexível o bastante para a aplicação prática, considerando os diversos estágios de implementação dos atuais sistemas supervisórios. O modelo evolucionário metaheurístico proposto foi aplicado para um caso ilustrativo evidenciando as suas potencialidades e os pontos a serem aprimorados. / This thesis aims at contributing for the estimation of electrical performance in the distribution of electrical energy. Electrical performance is assumed to be the evaluation of network congestion parameters, losses and voltage level. The development of this work was impelled due to distribution utilities compulsory measurement permanent campaigns, and due to the need of the regulatory agency in establishing operational performance standards, as stated in the Distribution Code of Aneel, the Brazilian Energy Regulatory Agency. The electrical performance estimation is formulated according to an optimization problem where the objective functions correspond to an evaluation of occurrence probability, and correspond to a proximity evaluation of calculated parameters with values obtained by measurement as well. Load values are discretized according to ocurrence probabilities within each interval, so that formulation results in a multiobjective combinatorial optimization of exponential dimension. Network reduction procedures to substantially reduce Decision Domain and network expansion procedures to recompose it are proposed. Specific heuristics are also proposed to get solutions with load diversity and unbalanced loads. In order to adequately apply these heuristics, a metaheuristic evolutionary method to build feasible solutions is proposed and applied, and ranked according to Pareto´s concept. For each dominance frontier or group of frontiers, the application builds the probabilistic: current and load flow distribution of for each branch, voltage level for each bar and circuit technical losses. The mathematical formulation of optimization is flexible enough to be effectively applied taking into account different levels of supervisory systems developed in the utilities. The metaheuristic evolutionary model proposed was applied to a representative case with main potentialities and weak points to be improved.
|
105 |
Evolutionary Clustering Search para Planejamento de Circulação de Trens de Carga / Evolutionary Clustering Search for Freight Train Circulation PlanningPINHEIRO, Eggo Henrique Freire 19 July 2017 (has links)
Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-10-31T20:55:43Z
No. of bitstreams: 1
eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) / Made available in DSpace on 2017-10-31T20:55:43Z (GMT). No. of bitstreams: 1
eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5)
Previous issue date: 2017-07-19 / Freight railways are the major means of transportation of bulk material, such as iron ore
from the origin to the destination. Usually for heavy haul railways, the destination is
a port. For the last few years there has been a fast growing demand. However, railway
infrastructure capacity increasing is very expensive and require a lot of investiment budget.
Therefore, an improvement of train scheduling process is needed to ensure the best and
efficient use of the current railway. Nevertheless, in some situations it is overwhelmingly
complex to solve, an NP-hard problem. Since all the previous work provided on the Train
Timetable Problem is usually only applied locally to a single railway, this work provides a
public base benchmark of test railways built by heuristcs. Moreover, this work deals with
the train timetabling problem applied to mixed traffic railways with both cargo trains and
passenger trains sharing the same resources with different priorities. It is proposed a new
mathematical model extended from literature previous work intended to avoid infeasible
solutions instead reparing or discarding on these cases. This model contains additional
support for parallel multi-track for several railway’s signaling system approaches context
as well as overtaking on it without deadlocks possibility. This model considers trains in
current position and future departure planned. To achieve an improved train scheduling is
applied the Evolutionary Clustering Search (ECS) with multi heuristics approaches and a
modified mutation operator of Genetic Algorithm as component of ECS. The experiments
shows ECS outperforms almost all tests scenario and the modified mutation operator
strongly improve the results / Ferrovias de trens de carga são os principais meios de transporte de materiais, tais como
minério de ferro, da sua origem até o seu destino. Geralmente para ferrovias de transporte
pesado, o destino é o porto. Nos últimos anos, a demanda de produção tem aumentado assim
como o uso da ferrovia para transportá-la, no entanto, a expansão da sua infraestrutura
requer um grande investimento. Assim, um planejamento de circulação de trens mais
efetivo que maximize a capacidade de tráfego se faz necessária. No entanto, em algumas
situações a sua otimização é bastante complexa para ser executada, um problema NP-Difícil.
Embora todo trabalho elaborado nesse tema é geralmente aplicado localmente em uma
única ferrovia, este trabalho provê uma base genérica de ferrovias gerado por heurísticas.
Além disso, esta dissertação lida com o problema de circulação de trens aplicado a ferrovias
mistas envolvendo trens de carga assim como trens de passageiros compartilhando o
mesmo recurso e com diferentes prioridades. É proposto um novo modelo matemático
estendido de um trabalho existente na literatura que procura evitar conflitos ao invés de
permitir soluções inviáveis, sendo necessário reparação delas ou descarte. Este modelo
lida com uma quantidade variável de linhas em locais de parada compatível com várias
abordagens de sistema de sinalização disponíveis, assim como considera ultrapassagens
de forma a evitar deadlocks, da mesma forma que trata contextos de trens em circulação
como planejados para realizar a otimização. Para encontrar boas soluções, ao planejamento
de circulação de trens é aplicado uma abordagem do Evolutionary Clustering Search
(ECS) com múltiplas heurísticas, e um operador de mutação modificado do Algoritmo
Genético como componente do ECS. Os experimentos computacionais mostraram que
o ECS superou quase todos os cenários de teste e o operador de mutação modificado
melhorou significativamente os resultados finais.
|
106 |
Técnicas de otimização combinatória multiobjetivo aplicadas na estimação do desempenho elétrico de redes de distribuição. / Multiobjective combinatorial optimization techniques applied on electrical performance estimation of distribution networks.Hashimoto, Kleber 27 September 2004 (has links)
Neste trabalho são apresentadas contribuições para a estimação do desempenho elétrico na distribuição de energia elétrica, com implicações nos mais diversos problemas da operação e do planejamento da distribuição. Entende-se por desempenho elétrico, a avaliação dos parâmetros de congestionamento de redes, as perdas e o nível de tensão. A motivação deste trabalho está na agregação dos esforços advindos da campanha de medição compulsória das concessionárias de distribuição e da necessidade do órgão regulador de estabelecer parâmetros de avaliação do desempenho operacional das empresas, como previsto no documento intitulado Procedimentos da Distribuição" da Aneel. A estimação do desempenho elétrico é formulada segundo um problema de otimização multiobjetivo onde as funções objetivo compõem uma avaliação de probabilidade de ocorrência e uma avaliação de proximidade dos parâmetros elétricos calculados com os valores obtidos por medição. Os valores das cargas são discretizados segundo probabilidades de ocorrência em cada intervalo, de modo que a formulação resulte em um problema de otimização combinatória multiobjetivo de dimensão exponencial. Propõe-se um procedimento de redução de rede, que diminua consideravelmente o espaço de decisões, e um procedimento de expansão de redes para recompô-la. Também são propostas heurísticas específicas para a obtenção de soluções com cargas diversificadas e desequilibradas. Para uma aplicação adequada destas heurísticas, propôs-se e aplicou-se um método evolucionário metaheurístico para composição das soluções factíveis, ordenadas de acordo com o conceito de dominância de Pareto. Para cada fronteira de dominância, ou conjunto de fronteiras, o aplicativo constrói a distribuição probabilística da corrente e fluxo de potência de cada trecho, o nível de tensão em todas as barras e as perdas técnicas totais do circuito. A formulação matemática de otimização é flexível o bastante para a aplicação prática, considerando os diversos estágios de implementação dos atuais sistemas supervisórios. O modelo evolucionário metaheurístico proposto foi aplicado para um caso ilustrativo evidenciando as suas potencialidades e os pontos a serem aprimorados. / This thesis aims at contributing for the estimation of electrical performance in the distribution of electrical energy. Electrical performance is assumed to be the evaluation of network congestion parameters, losses and voltage level. The development of this work was impelled due to distribution utilities compulsory measurement permanent campaigns, and due to the need of the regulatory agency in establishing operational performance standards, as stated in the Distribution Code of Aneel, the Brazilian Energy Regulatory Agency. The electrical performance estimation is formulated according to an optimization problem where the objective functions correspond to an evaluation of occurrence probability, and correspond to a proximity evaluation of calculated parameters with values obtained by measurement as well. Load values are discretized according to ocurrence probabilities within each interval, so that formulation results in a multiobjective combinatorial optimization of exponential dimension. Network reduction procedures to substantially reduce Decision Domain and network expansion procedures to recompose it are proposed. Specific heuristics are also proposed to get solutions with load diversity and unbalanced loads. In order to adequately apply these heuristics, a metaheuristic evolutionary method to build feasible solutions is proposed and applied, and ranked according to Pareto´s concept. For each dominance frontier or group of frontiers, the application builds the probabilistic: current and load flow distribution of for each branch, voltage level for each bar and circuit technical losses. The mathematical formulation of optimization is flexible enough to be effectively applied taking into account different levels of supervisory systems developed in the utilities. The metaheuristic evolutionary model proposed was applied to a representative case with main potentialities and weak points to be improved.
|
107 |
Aplicação de metaheurísticas para parametrização do módulo IPTV da plataforma de convergência digital - DIGICONVRodrigues, Robermilton Sant´Anna de Oliveira 10 June 2016 (has links)
Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2016-11-18T11:12:32Z
No. of bitstreams: 1
Robermilton Sant´Anna de Oliveira Rodrigues_.pdf: 3942890 bytes, checksum: cd68235e6f58b7b97f966958f932b60d (MD5) / Made available in DSpace on 2016-11-18T11:12:32Z (GMT). No. of bitstreams: 1
Robermilton Sant´Anna de Oliveira Rodrigues_.pdf: 3942890 bytes, checksum: cd68235e6f58b7b97f966958f932b60d (MD5)
Previous issue date: 2016-06-10 / IFRR - Instituto Federal de Educação Ciência e Tecnologia de Roraima / Com o advento da Internet, aliado à constante evolução das tecnologias de distribuição de Banda Larga, juntamente com um público cada vez mais exigente, surge o IPTV (Internet Protocol Television). Atualmente, existem várias pesquisas sobre como melhorar sua distribuição de conteúdo, através dos mais diversos dispositivos disponíveis no mercado, tais como: TV Digital, Tablets e Smartphones. Este trabalho apresenta uma ferramenta computacional, baseada em um modelo matemático, para otimização dos parâmetros do módulo IPTV de uma Plataforma de Convergência Digital (DIGICONV). Essa ferramenta computacional é baseada em aplicações das metaheurísticas Busca Tabu e Algoritmo Genético, a fim de obter melhorias em todos os segmentos da transmissão, além de identificar os motivos de uma possível sobrecarga do sistema, quando não há banda disponível suficiente para atender a todos os clientes, através de configurações específicas nos parâmetros de entrada que são: a taxa de transmissão (Tt), a qualidade de vídeo (Qv), a qualidade de áudio (Qa), os tipos de clientes (Tc), a largura de banda do cliente (Lb) e a quantidade de banda disponível (Bd). Os resultados obtidos neste trabalho comprovaram que tanto a Busca Tabu quanto o Algoritmo Genético obtiveram resultados satisfatórios e otimizados, conforme o aumento da Função Objetivo, atestando sua eficiência. / With the advent of the Internet, combined with the constant evolution of the broadband distribution technologies, along with the public increasingly demanding, IPTV (Internet Protocol Television) arises. Currently, there are several studies on how to improve the distribution of content through a variety of devices available in the market, such as Digital TV, Tablets and Smartphones. This paper presents a computational tool based on a mathematical model to optimize IPTV module parameters of a Digital Convergence Platform (DIGICONV). This software tool is based on applications of metaheuristics Tabu Search and Genetic Algorithm in order to achieve improvements in all segments of the transmission, and to identify the reasons for a possible system overload, when there is not enough available bandwidth to meet all customers through specific settings in the input parameters are: the transmission rate (Tt), the video quality (Qv), audio quality (Qa), the types of customers (Tc), the bandwidth of client (Lb) and the amount of available bandwidth (BD). The results of this study showed that both the tabu search and the genetic algorithm achieved satisfactory results and optimized, with increasing Objective Function, attesting to its effectiveness.
|
108 |
A Genetic Algorithm For The Location-routing Problem With Time WindowsOzgonenc, Hande 01 July 2006 (has links) (PDF)
The emphasis on minimizing the logistics costs to decrease overall system costs has led the researchers to consider the interdependencies between the decisions of locating facilities and planning the routes from those facilities. The location-routing problems considering this issue are the subject of this thesis study. A two-level hierarchical distribution system is considered in which goods are delivered from the sources (plants) to the facilities (depots) and then from the facilities to the customers. The facilities are uncapacitated and operate within the shift times defined. The goods are to be delivered to the customers within their time windows by the vehicles that are capacitated.
Both a mathematical model and a genetic algorithm based heuristic solution approach are proposed for this problem. We discuss the problem specific issues integrated with the general framework of the genetic algorithm applications. The computational studies are realized on a number of test problems. The results indicate
that the genetic algorithm based heuristic gives satisfactory results compared with a sequential solution methodology.
|
109 |
A Genetic Algorithm For The Multi-level Maximal Covering Ambulance Location ProblemKaraman, Mesut 01 September 2008 (has links) (PDF)
The emergency medical services (EMS) provide the preliminary assistance and transportation for patients in need of urgent medical care in order to decrease the mortality rate and reduce the non-reversible effects of injuries. Since the objective is directly related to the human life, the value of the proposed solutions in order to improve the performance of EMS is highly welcomed. Mainly, there are three problems that EMS managers face with: location, allocation and redeployment of the EMS facilities/vehicles. Most of the studies in EMS literature focus on accurately modeling the probabilistic nature of the availability of an ambulance when it is called for. However, trivial changes in model parameters or estimates could dramatically change the optimal allocations generated by the probabilistic models and hence make the model invalid. In this study, we formulate the ambulance location problem as a deterministic multi-level maximal coverage model by which the total demand is tried to be covered as many as possible at multiple levels. Both a mathematical programming model and genetic algorithm-based heuristic approaches are proposed for the problem. The results indicate that the genetic algorithm-based solutions give reliable (near-optimal) and robust results in reasonable computational times for the problem. Moreover, the tradeoffs between the two performance measures, &lsquo / responsiveness&rsquo / and &lsquo / preparedness&rsquo / , are searched for / and our approaches with multi-level coverage are compared against the multiple coverage approaches in terms of these performance measures.
|
110 |
Algorithms for irreducible infeasible subset detection in CSP - Application to frequency planning and graph k-coloringHu, Jun 27 November 2012 (has links) (PDF)
The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.
|
Page generated in 0.0735 seconds