Revelando os limites das heurísticas de pesquisa local aprendidas: você é o mais poderoso dos mansos?

Tabela de links

Resumo e introdução

Trabalho relatado

Avaliação para Max-Cut

Avaliação para SAT

Resumo e Outlook, Referências

Materiais Suplementares

Abstrato

Nos últimos anos, a combinação de redes neurais com heurísticas de busca local tornou-se popular no campo da otimização combinatória. Apesar de suas consideráveis demandas computacionais, esta abordagem apresentou resultados promissores com o mínimo de engenharia manual. No entanto, identificamos três limitações críticas na avaliação empírica destas tentativas de integração. Em primeiro lugar, os casos com complexidade moderada e bases de referência fracas representam um desafio na avaliação precisa da eficácia das abordagens baseadas na aprendizagem. Em segundo lugar, a ausência de um estudo de ablação torna difícil quantificar e atribuir melhorias com precisão à arquitetura de aprendizagem profunda. Por último, a generalização de heurísticas aprendidas em diversas distribuições permanece pouco explorada. Neste estudo, conduzimos uma investigação abrangente sobre essas limitações identificadas. Surpreendentemente, demonstramos que uma heurística aprendida simples baseada na Pesquisa Tabu supera as heurísticas aprendidas de última geração (SOTA) em termos de desempenho e generalização. Nossas descobertas desafiam as suposições prevalecentes e abrem caminhos interessantes para futuras pesquisas e inovações em otimização combinatória.

1. INTRODUÇÃO

Projetar heurísticas eficazes ou algoritmos de aproximação para problemas de otimização combinatória (CO) NP-difíceis é uma tarefa desafiadora, muitas vezes exigindo conhecimento de domínio e extensa tentativa e erro. Assim, a ideia de automatizar esse processo de projeto exigente e tedioso por meio de aprendizado de máquina para aprender algoritmos que exploram a estrutura inerente de um problema ganhou interesse significativo entre os pesquisadores (Bello et al., 2016; Khalil et al., 2017; Bengio et al., 2016; Khalil et al., 2017; Bengio et al., 2016; Khalil et al., 2017; Bengio et al. ., 2021; Dong et al., 2021). Particularmente, uma parte considerável desses trabalhos (Khalil et al., 2017; Barrett et al., 2020; Yolcu e P´oczos, 2019) concentrou-se no emprego de Redes Neurais de Grafos (GNNs) para problemas de CO. Apesar das demandas computacionais, essas abordagens baseadas em GNN demonstraram desempenho competitivo em comparação com heurísticas SOTA adaptadas para problemas específicos.

Embora esses avanços potenciais sejam muito promissores, algumas preocupações permanecem. O desempenho superior das heurísticas aprendidas pode ser atribuído à seleção de instâncias e linhas de base específicas. Especificamente, se as linhas de base forem fracas, as heurísticas aprendidas podem facilmente superá-las. Sem instâncias difíceis e seleção de linha de base adequada, as heurísticas aprendidas podem facilmente mostrar desempenho comparável com as heurísticas SOTA, e isso pode levar a uma superestimação das capacidades reais das heurísticas aprendidas. Além disso, as comparações com as heurísticas SOTA são ocasionalmente deixadas de lado devido aos desafios de escalabilidade com arquiteturas de aprendizagem profunda.

Um subconjunto de abordagens baseadas na aprendizagem (Khalil et al., 2017; Yolcu e P´oczos, 2019; Barrett et al., 2020, 2022) incorpora a funcionalidade ou comportamento das heurísticas tradicionais, potencialmente oferecendo desempenho melhorado ou melhorado através da integração de heurísticas princípios com componentes de aprendizado de máquina. Se faltar uma comparação abrangente com a heurística integrada e um estudo de ablação da arquitetura de aprendizagem profunda, torna-se um desafio determinar a contribuição específica da arquitetura de aprendizagem profunda. Consequentemente, se as heurísticas integradas forem robustas, as heurísticas aprendidas podem superar perfeitamente as heurísticas de base, enquanto a arquitetura de aprendizagem profunda desempenha um pequeno papel.

Outra grande conquista da heurística aprendida (Khalil et al., 2017; Barrett et al., 2020; Toenshof et al., 2019), inicialmente treinada em instâncias menores e específicas de uma determinada distribuição, exibe desempenho impressionante quando testada em instâncias maiores de distribuições diferentes. Esta conquista é uma conquista significativa, alinhando-se com o objetivo central de empregar abordagens baseadas na aprendizagem: mitigar a necessidade de ampla personalização e conhecimento específico de domínio, muitas vezes exigido pela heurística. Embora as heurísticas clássicas com hiperparâmetros também possam encontrar desafios se forem ajustadas para uma distribuição específica, elas também podem generalizar entre diferentes distribuições. A investigação primária gira em torno de se as heurísticas aprendidas realmente demonstram uma generalização superior em comparação com as heurísticas clássicas. Uma comparação completa e perspicaz das heurísticas aprendidas com as heurísticas clássicas fornece insights valiosos sobre a generalização das heurísticas aprendidas.

As heurísticas aprendidas muitas vezes carecem de garantias teóricas, tornando a avaliação empírica o único método para compreender os pontos fortes e as limitações das metodologias propostas. Acreditamos que várias questões fundamentais, mas cruciais, permanecem inexploradas na avaliação empírica destes trabalhos. Embora essas perguntas sejam pertinentes a todos os tipos de heurísticas aprendidas, nós as perguntamos e respondemos analisando publicações altamente citadas e recentes revisadas por pares focadas no aprendizado de heurísticas de busca local. Nosso objetivo não é fornecer referências exaustivas para os problemas de CO discutidos em nosso trabalho, mas sim auxiliar futuros pesquisadores na avaliação de suas pesquisas.

Concretamente, fazemos e respondemos às seguintes perguntas:

1. A heurística aprendida pode ser superparametrizada? Absolutamente. Substituindo o GNN no ECO-DQN por regressão linear e utilizando um subconjunto de recursos do ECO-DQN (Barrett et al., 2020) vinculado à Pesquisa Tabu (Glover, 1990), introduzimos uma versão podada do ECO-DQN denominada SoftTabu . Nosso estudo demonstra que SoftTabu apresenta desempenho superior e generalização em comparação com ECO-DQN para o problema NPhard Maximum-Cut (Max-Cut).

2. O viés da linha de base pode ser atribuído ao desempenho superior das heurísticas aprendidas? Sim, demonstramos que SoftTabu, uma heurística aprendida vanilla, pode superar S2V-DQN (Khalil et al., 2017) para o problema Max-Cut e GNNSAT (Yolcu e P´oczos, 2019) para Satisfiabilidade Booleana (SAT).

*3. As heurísticas aprendidas podem demonstrar generalização superior devido ao viés de seleção de instâncias?*Sim, demonstramos que ECO-DQN mostra generalização pobre em instâncias mais difíceis e fica facilmente preso no espaço de busca.