« May 2018 | Main

Thursday, June 14, 2018

Simulated Annealing: The Travelling Salesman Problem

The travelling salesman problem—finding the shortest itinerary to visit each of a number of cities—is a classic of combinatorial optimisation. Finding optimal solutions by brute force is effectively impossible: there are more than 1032 possible paths to visit thirty cities, and if you could test a billion paths a second, it would take 600,000 times the age of the universe to compare them all and choose the shortest.

If you don't require an absolutely optimal solution, but rather one that's within a few percent of the best possible, there are a number of optimisation techniques which will get the job done. A new interactive page, Simulated Annealing: The Travelling Salesman Problem, explores one of the most elegant, simulated annealing. By analogy to creating large scale order by annealing metal, random perturbations to a path, performed according to a schedule where the degree of perturbation (“temperature”) steadily decreases, finds near-optimal solutions to even very large problems. You can experiment with the cost function and observe its effect on the solutions found. A number of standard test cases, some of which have known optimal solutions, are included.

This page runs entirely within your browser using JavaScript and HTML5 canvas graphics. There is no need to download, build, or install any software to use it.

Posted at 13:55 Permalink

Tuesday, June 12, 2018

Reading List: Influx

Suarez, Daniel. Influx. New York: Signet, [2014] 2015. ISBN 978-0-451-46944-1.
Doesn't it sometimes seem that, sometime in the 1960s, the broad march of technology just stopped? Certainly, there has been breathtaking progress in some fields, particularly computation and data communication, but what about clean, abundant fusion power too cheap to meter, opening up the solar system to settlement, prevention and/or effective treatment of all kinds of cancer, anti-aging therapy, artificial general intelligence, anthropomorphic robotics, and the many other wonders we expected to be commonplace by the year 2000?

Decades later, Jon Grady was toiling in his obscure laboratory to make one of those dreams—gravity control— a reality. His lab is invaded by notorious Luddite terrorists who plan to blow up his apparatus and team. The fuse burns down into the charge, and all flashes white, then black. When he awakes, he finds himself, in good condition, in a luxurious office suite in a skyscraper, where he is introduced to the director of the Federal Bureau of Technology Control (BTC). The BTC, which appears in no federal organisation chart or budget, is charged with detecting potentially emerging disruptive technologies, controlling and/or stopping them (including deploying Luddite terrorists, where necessary), co-opting their developers into working in deep secrecy with the BTC, and releasing the technologies only when human nature and social and political institutions were “ready” for them—as determined by the BTC.

But of course those technologies exist within the BTC, and it uses them: unlimited energy, genetically engineered beings, clones, artificial intelligence, and mind control weapons. Grady is offered a devil's bargain: join the BTC and work for them, or suffer the worst they can do to those who resist and see his life's work erased. Grady turns them down.

At first, his fate doesn't seem that bad but then, as the creative and individualistic are wont to do, he resists and discovers the consequences when half a century's suppressed technologies are arrayed against a defiant human mind. How is he to recover his freedom and attack the BTC? Perhaps there are others, equally talented and defiant, in the same predicament? And, perhaps, the BTC, with such great power at its command, is not so monolithic and immune from rivalry, ambition, and power struggles as it would like others to believe. And what about other government agencies, fiercely protective of their own turf and budgets, and jealous of any rivals?

Thus begins a technological thriller very different from the author's earlier Dæmon (August 2010) and Freedom™ (January 2011), but compelling. How does a band of individuals take on an adversary which can literally rain destruction from the sky? What is the truth beneath the public face of the BTC? What does a superhuman operative do upon discovering everything has been a lie? And how can one be sure it never happens again?

With this novel Daniel Suarez reinforces his reputation as an emerging grand master of the techno-thriller. This book won the 2015 Prometheus Award for best libertarian novel.

Posted at 22:24 Permalink

Wednesday, June 6, 2018

Reading List: Enemy of the State

Mills, Kyle. Enemy of the State. New York: Atria Books, 2017. ISBN 978-1-4767-8351-2.
This is the third novel in the Mitch Rapp saga written by Kyle Mills, who took over the franchise after the death of Vince Flynn, its creator. It is the sixteenth novel in the Mitch Rapp series (Flynn's first novel, Term Limits [November 2009], is set in the same world and shares characters with the Mitch Rapp series, but Rapp does not appear in it, so it isn't considered a Rapp novel), Mills continues to develop the Rapp story in new directions, while maintaining the action-packed and detail-rich style which made the series so successful.

When a covert operation tracking the flow of funds to ISIS discovers that a (minor) member of the Saudi royal family is acting as a bagman, the secret deal between the U.S. and Saudi Arabia struck in the days after the 2001 terrorist attacks on the U.S.—the U.S. would hide the ample evidence of Saudi involvement in the plot in return for the Saudis dealing with terrorists and funders of terrorism within the Kingdom—is called into question. The president of the U.S., who might be described in modern jargon as “having an anger management problem” decides the time has come to get to the bottom of what the Saudis are up to: is it a few rogue ne'er-do-wells, or is the leadership up to their old tricks of funding and promoting radical Islamic infiltration and terrorism in the West? And if they are, he wants to make them hurt, so they don't even think about trying it again.

When it comes to putting the hurt on miscreants, the president's go-to-guy is Mitch Rapp, the CIA's barely controlled loose cannon, who has a way of getting the job done even if his superiors don't know, and don't want to know, the details. When the president calls Rapp into his office and says, “I think you need to have a talk … and at the end of that talk I think he needs to be dead” there is little doubt about what will happen after Rapp walks out of the office.

But there is a problem. Saudi Arabia is, nominally at least, an important U.S ally. It keeps the oil flowing and prices down, not only benefitting the world economy, but putting a lid on the revenue of troublemakers such as Russia and Iran. Saudi Arabia is a major customer of U.S. foreign military sales. Saudi Arabia is also a principal target of Islamic revolutionaries, and however bad it is today, one doesn't want to contemplate a post-Saudi regime raising the black flag of ISIS, crying havoc, and letting slip the goats of war. Wet work involving the royal family must not just be deniable but totally firewalled from any involvement by the U.S. government. In accepting the mission Rapp understands that if things blow up, he will not only be on his own but in all likelihood have the U.S. government actively hunting him down.

Rapp hands in his resignation to the CIA, ending a relationship which has existed over all of the previous novels. He meets with his regular mission team and informs them he “need[s] to go somewhere you … can't follow”: involving them would create too many visible ties back to the CIA. If he's going to go rogue, he decides he must truly do so, and sets off assembling a rogues' gallery, composed mostly of former adversaries we've met in previous books. When he recruits his friend Claudia, who previously managed logistics for an assassin Rapp confronted in the past, she says, “So, a criminal enterprise. And only one of the people at this table knows how to be a criminal.”

Assembling this band of dodgy, dangerous, and devious characters at the headquarters of an arms dealer in that paradise which is Juba, South Sudan, Rapp plots an operation to penetrate the security surrounding the Saudi princeling and find out how high the Saudi involvement in funding ISIS goes. What they learn is disturbing in the extreme.

After an operation gone pear-shaped, and with the CIA, FBI, Saudis, and Sudanese factions all chasing him, Rapp and his misfit mob have to improvise and figure out how to break the link between the Saudis and ISIS in way which will allow him to deny everything and get back to whatever is left of his life.

This is a thriller which is full of action, suspense, and characters fans of the series will have met before acting in ways which may be surprising. After a shaky outing in the previous installment, Order to Kill (December 2017), Kyle Mills has regained his stride and, while preserving the essentials of Mitch Rapp, is breaking new ground. It will be interesting to see if the next novel, Red War, expected in September 2018, continues to involve any of the new team. While you can read this as a stand-alone thriller, you'll enjoy it more if you've read the earlier books in which the members of Rapp's team were principal characters.

Posted at 22:30 Permalink

Saturday, June 2, 2018

Reading List: Project Cyclops

Oliver, Bernard M., John Billingham, et al. Project Cyclops. Stanford, CA: Stanford/NASA Ames Research Center, 1971. NASA-CR-114445 N73-18822.
There are few questions in science as simple to state and profound in their implications as “are we alone?”—are humans the only species with a technological civilisation in the galaxy, or in the universe? This has been a matter of speculation by philosophers, theologians, authors of fiction, and innumerable people gazing at the stars since antiquity, but it was only in the years after World War II, which had seen the development of high-power microwave transmitters and low-noise receivers for radar, that it dawned upon a few visionaries that this had now become a question which could be scientifically investigated.

The propagation of radio waves through the atmosphere and the interstellar medium is governed by basic laws of physics, and the advent of radio astronomy demonstrated that many objects in the sky, some very distant, could be detected in the microwave spectrum. But if we were able to detect these natural sources, suppose we connected a powerful transmitter to our radio telescope and sent a signal to a nearby star? It was easy to calculate that, given the technology of the time (around 1960), existing microwave transmitters and radio telescopes could transmit messages across interstellar distances.

But, it's one thing to calculate that intelligent aliens with access to microwave communication technology equal or better than our own could communicate over the void between the stars, and entirely another to listen for those communications. The problems are simple to understand but forbidding to face: where do you point your antenna, and where do you tune your dial? There are on the order of a hundred billion stars in our galaxy. We now know, as early researchers suspected without evidence, that most of these stars have planets, some of which may have conditions suitable for the evolution of intelligent life. Suppose aliens on one of these planets reach a level of technological development where they decide to join the “Galactic Club” and transmit a beacon which simply says “Yo! Anybody out there?” (The beacon would probably announce a signal with more information which would be easy to detect once you knew where to look.) But for the beacon to work, it would have to be aimed at candidate stars where others might be listening (a beacon which broadcasted in all directions—an “omnidirectional beacon”—would require so much energy or be limited to such a short range as to be impractical for civilisations with technology comparable to our own).

Then there's the question of how many technological communicating civilisations there are in the galaxy. Note that it isn't enough that a civilisation have the technology which enables it to establish a beacon: it has to do so. And it is a sobering thought that more than six decades after we had the ability to send such a signal, we haven't yet done so. The galaxy may be full of civilisations with our level of technology and above which have the same funding priorities we do and choose to spend their research budget on intersectional autoethnography of transgender marine frobdobs rather than communicating with nerdy pocket-protector types around other stars who tediously ask Big Questions.

And suppose a civilisation decides it can find the spare change to set up and operate a beacon, inviting others to contact it. How long will it continue to transmit, especially since it's unlikely, given the finite speed of light and the vast distances between the stars, there will be a response in the near term? Before long, scruffy professors will be marching in the streets wearing frobdob hats and rainbow tentacle capes, and funding will be called into question. This is termed the “lifetime” of a communicating civilisation, or L, which is how long that civilisation transmits and listens to establish contact with others. If you make plausible assumptions for the other parameters in the Drake equation (which estimates how many communicating civilisations there are in the galaxy), a numerical coincidence results in the estimate of the number of communicating civilisations in the galaxy being roughly equal to their communicating life in years, L. So, if a typical civilisation is open to communication for, say, 10,000 years before it gives up and diverts its funds to frobdob research, there will be around 10,000 such civilisations in the galaxy. With 100 billion stars (and around as many planets which may be hosts to life), that's a 0.00001% chance that any given star where you point your antenna may be transmitting, and that has to be multiplied by the same probability they are transmitting their beacon in your direction while you happen to be listening. It gets worse. The galaxy is huge—around 150 million light years in diameter, and our technology can only communicate with comparable civilisations out to a tiny fraction of this, say 1000 light years for high-power omnidirectional beacons, maybe ten to a hundred times that for directed beacons, but then you have the constraint that you have to be listening in their direction when they happen to be sending.

It seems hopeless. It may be. But the 1960s were a time very different from our constrained age. Back then, if you had a problem, like going to the Moon in eight years, you said, “Wow! That's a really big nail. How big a hammer do I need to get the job done?” Toward the end of that era when everything seemed possible, NASA convened a summer seminar at Stanford University to investigate what it would take to seriously investigate the question of whether we are alone. The result was Project Cyclops: A Design Study of a System for Detecting Extraterrestrial Intelligent Life, prepared in 1971 and issued as a NASA report (no Library of Congress catalogue number or ISBN was assigned) in 1973; the link will take you to a NASA PDF scan of the original document, which is in the public domain. The project assembled leading experts in all aspects of the technologies involved: antennas, receivers, signal processing and analysis, transmission and control, and system design and costing.

They approached the problem from what might be called the “Apollo perspective”: what will it cost, given the technology we have in hand right now, to address this question and get an answer within a reasonable time? What they came up with was breathtaking, although no more so than Apollo. If you want to listen for beacons from communicating civilisations as distant as 1000 light years and incidental transmissions (“leakage”, like our own television and radar emissions) within 100 light years, you're going to need a really big bucket to collect the signal, so they settled on 1000 dishes, each 100 metres in diameter. Putting this into perspective, 100 metres is about the largest steerable dish anybody envisioned at the time, and they wanted to build a thousand of them, densely packed.

But wait, there's more. These 1000 dishes were not just a huge bucket for radio waves, but a phased array, where signals from all of the dishes (or a subset, used to observe multiple targets) were combined to provide the angular resolution of a single dish the size of the entire array. This required breathtaking precision of electronic design at the time which is commonplace today (although an array of 1000 dishes spread over 16 km would still give most designers pause). The signals that might be received would not be fixed in frequency, but would drift due to Doppler shifts resulting from relative motion of the transmitter and receiver. With today's computing hardware, digging such a signal out of the raw data is something you can do on a laptop or mobile phone, but in 1971 the best solution was an optical data processor involving exposing, developing, and scanning film. It was exquisitely clever, although obsolete only a few years later, but recall the team had agreed to use only technologies which existed at the time of their design. Even more amazing (and today, almost bizarre) was the scheme to use the array as an imaging telescope. Again, with modern computers, this is a simple matter of programming, but in 1971 the designers envisioned a vast hall in which the signals from the antennas would be re-emitted by radio transmitters which would interfere in free space and produce an intensity image on an image surface where it would be measured by an array of receiver antennæ.

What would all of this cost? Lots—depending upon the assumptions used in the design (the cost was mostly driven by the antenna specifications, where extending the search to shorter wavelengths could double the cost, since antennas had to be built to greater precision) total system capital cost was estimated as between 6 and 10 billion dollars (1971). Converting this cost into 2018 dollars gives a cost between 37 and 61 billion dollars. (By comparison, the Apollo project cost around 110 billion 2018 dollars.) But since the search for a signal may “almost certainly take years, perhaps decades and possibly centuries”, that initial investment must be backed by a long-term funding commitment to continue the search, maintain the capital equipment, and upgrade it as technology matures. Given governments' record in sustaining long-term efforts in projects which do not line politicians' or donors' pockets with taxpayer funds, such perseverance is not the way to bet. Perhaps participants in the study should have pondered how to incorporate sufficient opportunities for graft into the project, but even the early 1970s were still an idealistic time when we didn't yet think that way.

This study is the founding document of much of the work in the Search for Extraterrestrial Intelligence (SETI) conducted in subsequent decades. Many researchers first realised that answering this question, “Are we alone?”, was within our technological grasp when chewing through this difficult but inspiring document. (If you have an equation or chart phobia, it's not for you; they figure on the majority of pages.) The study has held up very well over the decades. There are a number of assumptions we might wish to revise today (for example, higher frequencies may be better for interstellar communication than were assumed at the time, and spread spectrum transmissions may be more energy efficient than the extreme narrowband beacons assumed in the Cyclops study).

Despite disposing of wealth, technological capability, and computing power of which authors of the Project Cyclops report never dreamed, we only make little plans today. Most readers of this post, in their lifetimes, have experienced the expansion of their access to knowledge in the transition from being isolated to gaining connectivity to a global, high-bandwidth network. Imagine what it means to make the step from being confined to our single planet of origin to being plugged in to the Galactic Web, exchanging what we've learned with a multitude of others looking at things from entirely different perspectives. Heck, you could retire the entire capital and operating cost of Project Cyclops in the first three years just from advertising revenue on frobdob videos! (Did I mention they have very large eyes which are almost all pupil? Never mind the tentacles.)

This document has been subjected to intense scrutiny over the years. The SETI League maintains a comprehensive errata list for the publication.

Posted at 21:30 Permalink